www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Idea: "Frozen" inner function

reply Michael Butscher <mbutscher gmx.de> writes:
Hi,

this is yet another idea how to return delegates from a function 
without destroying the context (which could be on the stack).


An inner function could get "frozen" as some kind of storage class 
which means that all variables accessed by the inner function which are 
defined in the surrounding function keep the value they had at the 
point in time when the inner function was defined.

Technically the context pointer of the inner function would point to an 
area on the heap. When the point of definition of the inner function is 
reached (which can happen multiple times) the needed variables are 
copied from the stackframe of the outer function to the context area of 
the inner function on the heap.



Example:


import std.stdio;

void main()
{
    int i = 0;
    
    while (i < 10)
    {
        frozen void pr() // when reached, i is copied to context
        {
            writef(i, " ");
        }
        
        ++i;  // pr() doesn't care about this change
        pr();
    }
}

Without "frozen" this prints:
1 2 3 4 5 6 7 8 9 10

With "frozen" this would print:
0 1 2 3 4 5 6 7 8 9


Of course you would put the definition only inside such a loop if you 
need it for some special reason.



Maybe it would also be desirable to trigger the copying of stackframe 
data at another point than function definition.

For this, a property "freeze" could be created for the inner function, 
so the above code could also look like:


import std.stdio;

void main()
{
    int i = 0;

    frozen void pr()
    {
        writef(i, " ");
    }
    
    while (i < 10)
    {
        pr.freeze;
        ++i;  // pr() doesn't care about this change
        pr();
    }
}


But this might be more complicated as the scope at function definition 
could be another than at the "freeze" call.



Michael
Nov 24 2006
next sibling parent David Medlock <noone nowhere.com> writes:
Michael Butscher wrote:
 Hi,
 
 
 Michael

These are a good idea. These are called closures. -DavidM
Nov 24 2006
prev sibling next sibling parent reply Steve Horne <stephenwantshornenospam100 aol.com> writes:
On Fri, 24 Nov 2006 21:59:33 +0100, Michael Butscher
<mbutscher gmx.de> wrote:

An inner function could get "frozen" as some kind of storage class 
which means that all variables accessed by the inner function which are 
defined in the surrounding function keep the value they had at the 
point in time when the inner function was defined.

It's called a closure. D inner functions seem to borrow a lot from the Pascal family languages. These have inner functions, but don't have closures. It simply isn't the done thing to call these inner functions using a pointer after the outer function had exited - it isn't part of structured programming. Closures originally came about in languages that have 'first class functions' - functional languages. These days, some scripting languages have them - Python uses them for 'lambda' anonymous functions, for instance. But it is a trade-off between efficiency and flexibility. D currently goes with efficiency by default, but you can explicitly create an inner function with a closure if you need one - though its not very convenient. Tip - use an anonymous class with a function-call method. Of course, a shorthand for doing this is a good idea. -- Remove 'wants' and 'nospam' from e-mail.
Nov 24 2006
parent reply Michael Butscher <mbutscher gmx.de> writes:
Steve Horne wrote:
 On Fri, 24 Nov 2006 21:59:33 +0100, Michael Butscher
 <mbutscher gmx.de> wrote:
 
An inner function could get "frozen" as some kind of storage class 
which means that all variables accessed by the inner function which are 
defined in the surrounding function keep the value they had at the 
point in time when the inner function was defined.

It's called a closure. D inner functions seem to borrow a lot from the Pascal family languages. These have inner functions, but don't have closures. It simply isn't the done thing to call these inner functions using a pointer after the outer function had exited - it isn't part of structured programming. Closures originally came about in languages that have 'first class functions' - functional languages. These days, some scripting languages have them - Python uses them for 'lambda' anonymous functions, for instance.

I heard about closures already, but I thought that they are different from inner functions only by surviving the end of the outer function. Especially a closure would have direct access to the current value of local variables of the outer function (if it exists yet) which is not the case for frozen functions.
 But it is a trade-off between efficiency and flexibility. D currently
 goes with efficiency by default, but you can explicitly create an
 inner function with a closure if you need one - though its not very
 convenient.

The only efficiency tradeoff of frozen functions is the copying at the time of definition (and later the freeing of the context memory). Except for that they would be as efficient as inner functions.
 Tip - use an anonymous class with a function-call method.

This would be technically the same, but, as you wrote, less convenient. Michael
Nov 25 2006
next sibling parent reply "Jarrett Billingsley" <kb3ctd2 yahoo.com> writes:
"Michael Butscher" <mbutscher gmx.de> wrote in message 
news:MPG.1fd2668cdc5c74998969d news.digitalmars.com...

 The only efficiency tradeoff of frozen functions is the copying at the
 time of definition (and later the freeing of the context memory).
 Except for that they would be as efficient as inner functions.

If in a loop, or in a function which is called a lot, that would be a lot of allocations, which is particularly wasteful if you never return the closure from the function. I'd say a very large percentage of the time, you don't need to return nested functions, so it'd be wasteful to enable the feature when it's not used that often. Additionally, there's the problem of functions with several levels of nesting. If you have c() inside b() inside a(), if c() accesses local variables of both b() and a(), when b() returns (but still inside a()), the closure of c() will have to be able to access the active locals of a() on the stack, but the locals of b() will have to be on the heap. This would have to be done through some second level of indirection or using multiple context pointers. This problem exists in languages such as Lua (and mine, MiniD!) and is handled with tricky things called upvalues, which are a second level of indirection for each outer function local. I don't know how well something like that would fit into a lower-level language like D.
 This would be technically the same, but, as you wrote, less convenient.

For the time being, though, it's certainly a nice (and simple) alternative / workaround. It also has the advantage that you can very selectively control if/when the closure's context is allocated on the heap.
Nov 25 2006
parent Michael Butscher <mbutscher gmx.de> writes:
Jarrett Billingsley wrote:
 "Michael Butscher" <mbutscher gmx.de> wrote in message 
 news:MPG.1fd2668cdc5c74998969d news.digitalmars.com...
 
 The only efficiency tradeoff of frozen functions is the copying at the
 time of definition (and later the freeing of the context memory).
 Except for that they would be as efficient as inner functions.

If in a loop, or in a function which is called a lot, that would be a lot of allocations, which is particularly wasteful if you never return the closure from the function.

It is up to the programmer to place the definition of the "closure" at a point where it is only executed if needed, e.g. it could be placed directly before it is returned by the outer function. The allocation of the heap could be executed only when reaching the definition of the frozen function. My example might have been a bit misleading.
  I'd say a very large percentage of the time, you don't 
 need to return nested functions, so it'd be wasteful to enable the feature 
 when it's not used that often.

One field of application would also be to create small event handlers for GUI events. This happens more often, I think. But maybe it is really not needed so often, but I remember that there were already some discussions about closures, so I wanted to propose this simpler alternative.
 Additionally, there's the problem of functions with several levels of 
 nesting.  If you have c() inside b() inside a(), if c() accesses local 
 variables of both b() and a(), when b() returns (but still inside a()), the 
 closure of c() will have to be able to access the active locals of a() on 
 the stack, but the locals of b() will have to be on the heap.

If c() would be defined frozen, it just has all variables declared in c () itself on the stack and all variables declared somewhere outside on the heap (as a copy). It does especially NOT access the active locals of a(), but the locals as they were when c() was defined. If the original outside-variables exist on the stack yet is totally irrelevant.
  This would 
 have to be done through some second level of indirection or using multiple 
 context pointers.  This problem exists in languages such as Lua (and mine, 
 MiniD!) and is handled with tricky things called upvalues, which are a 
 second level of indirection for each outer function local.  I don't know how 
 well something like that would fit into a lower-level language like D.

Therefore my proposal is much simpler to realize than that.
 This would be technically the same, but, as you wrote, less convenient.

For the time being, though, it's certainly a nice (and simple) alternative / workaround. It also has the advantage that you can very selectively control if/when the closure's context is allocated on the heap.

But I also have to remember which outer variables are accessed. If I change the code of the inner function I could forget to copy a variable or copy unnecessary variables. My idea is not new but just more convenient and less error prone than the anonymous class technique. Michael
Nov 26 2006
prev sibling parent reply Steve Horne <stephenwantshornenospam100 aol.com> writes:
On Sat, 25 Nov 2006 14:41:49 +0100, Michael Butscher
<mbutscher gmx.de> wrote:

Especially a closure would have direct access to the current value of 
local variables of the outer function (if it exists yet) which is not 
the case for frozen functions.

That's not the definition of closures I was taught. A closure would behave exactly as your frozen function does - it does not have direct access to the current value since it keeps a copy of the value at the time when the definition was 'executed'. So for instance, in Python (which does use closures)... a = 5 fn = lambda : a a = 6 print fn() The output should be 5, not 6 - the value when the lambda expression was evaluated. Is it possible that you're being misled by the style of closures used for generics? They tend to mostly hold function pointers (pointers to the methods for the type that the generic is specialised for), but could possibly hold pointers to global variables too. -- Remove 'wants' and 'nospam' from e-mail.
Nov 25 2006
next sibling parent reply "Frank Benoit (keinfarbton)" <benoit tionex.removethispart.de> writes:
This is the case for Java also. If you define a anonymous class in a
method it can access the local variable and arguments of the surrounding
method. The compiler forces them to be final.

This is exactly like finding all references to the surrounding method,
and make a copy of all accessed vars.

e.g.

class MyClass{
  int    fld_i;
  double fld_d;
  void f( final int i, double d ){
    ListenerType l = new ListenerType(){
      void event( ){
        fld_i = i; // OK
        fld_i++;   // OK
        i++;       // Error, i is final
        fld_d = d; // Error, can only access final variables
      }
    }
  }
}
Nov 26 2006
parent reply Michael Butscher <mbutscher gmx.de> writes:
Frank Benoit (keinfarbton) wrote:

 This is the case for Java also. If you define a anonymous class in a
 method it can access the local variable and arguments of the surrounding
 method. The compiler forces them to be final.

My idea was inspired by this. As D has nothing like final, I thought a copy of the outer variables would do as well. Michael
Nov 26 2006
parent "Frank Benoit (keinfarbton)" <benoit tionex.removethispart.de> writes:
 My idea was inspired by this. As D has nothing like final, I thought a 
 copy of the outer variables would do as well.

I am not completely sure, but I think this is the way java implements this. If you imagine that the method can be called multiple times and the instantiated object can work with different final values, it seams the values are copied into the object instance.
Nov 26 2006
prev sibling parent reply Michael Butscher <mbutscher gmx.de> writes:
Steve Horne wrote:
 On Sat, 25 Nov 2006 14:41:49 +0100, Michael Butscher
 <mbutscher gmx.de> wrote:
 
Especially a closure would have direct access to the current value of 
local variables of the outer function (if it exists yet) which is not 
the case for frozen functions.

That's not the definition of closures I was taught. A closure would behave exactly as your frozen function does - it does not have direct access to the current value since it keeps a copy of the value at the time when the definition was 'executed'.

I could not find yet such a clear definition, e.g. http://en.wikipedia.org/wiki/Closure_(computer_science) says A closure typically comes about when one function is declared entirely within the body of another, and the inner function refers to local variables of the outer function. At runtime, when the outer function executes, a closure is formed. It consists of the inner function's code and references to any variables in the outer function's scope that the closure needs. which is not clear about that.
 So for instance, in Python (which does use closures)...
 
 a = 5
 fn = lambda : a
 a = 6
 print fn()
 
 The output should be 5, not 6 - the value when the lambda expression
 was evaluated.

Have you tried that? With Python 2.5 in an interactive session, I get:
 def test():



fn = lambda : a a = 6 print fn()
 test()



Michael
Nov 26 2006
parent reply Steve Horne <stephenwantshornenospam100 aol.com> writes:
On Sun, 26 Nov 2006 15:28:03 +0100, Michael Butscher
<mbutscher gmx.de> wrote:

Steve Horne wrote:

 So for instance, in Python (which does use closures)...
 
 a = 5
 fn = lambda : a
 a = 6
 print fn()
 
 The output should be 5, not 6 - the value when the lambda expression
 was evaluated.

Have you tried that? With Python 2.5 in an interactive session, I get:
 def test():



fn = lambda : a a = 6 print fn()
 test()




No, I didn't test, and now I'm a bit embarrassed, and confused. I have tonnes of code that uses lambdas, and I'm sure some depends on this behaviour. Code which is heavily used and which all seems to work. Yet suddenly, I can't get a simple example to work right. All I can say is that something's going on in Python that I don't know about. I've checked my favorite compiler-stuff text (Modern Compiler Design, Dick Grune et al) and theres a section (6.3.5.5 Currying a routine) that seems to agree with my closure definition more-or-less. But this is about currying, not inner functions. In the same book, section 6.3.5.3 is directly relevant (title "Returning a nested routine as a value"). It describes the using-dead-variables issue, but actually suggests keeping the local variables for the outer function in a heap frame rather than on the stack. But... 1 This is the variables for the outer function, not the inner function. You put those variables in the stack frame whether the inner function object is actually created or not, and several inner function objects could be created that all refer to the same stack frame. 2 It doesn't use the term closure to describe this. So basically, I thought I knew what I was talking about, but now I'm not so sure. Maybe Python is doing the (1) thing, but that leaves me wondering how come my existing code is working. Incidentally, Amazon seems to have the full text of the book if you want to check exactly what it says, but stepping through the pages one-by-one to get to the relevant section (around page 490-ish) is painful. -- Remove 'wants' and 'nospam' from e-mail.
Nov 26 2006
next sibling parent Steve Horne <stephenwantshornenospam100 aol.com> writes:
On Mon, 27 Nov 2006 07:40:00 +0000, Steve Horne
<stephenwantshornenospam100 aol.com> wrote:

1  This is the variables for the outer function, not the inner
   function. You put those variables in the stack frame whether
   the inner function object is actually created or not, and
   several inner function objects could be created that all refer
   to the same stack frame.

Ooops - that's... to the same *heap* frame. -- Remove 'wants' and 'nospam' from e-mail.
Nov 26 2006
prev sibling next sibling parent reply Michael Butscher <mbutscher gmx.de> writes:
Steve Horne wrote:
 But...
 
 1  This is the variables for the outer function, not the inner
    function. You put those variables in the stack frame whether
    the inner function object is actually created or not, and
    several inner function objects could be created that all refer
    to the same stack frame.
 
 2  It doesn't use the term closure to describe this.
 
 So basically, I thought I knew what I was talking about, but now I'm
 not so sure.
 
 Maybe Python is doing the (1) thing, but that leaves me wondering how
 come my existing code is working.

Before closures were introduced in Python (about 2.2 or so), it was a common idiom to write: lambda a=a: ... to access an outer variable a. Maybe you are using something like that.
 Incidentally, Amazon seems to have the full text of the book if you
 want to check exactly what it says, but stepping through the pages
 one-by-one to get to the relevant section (around page 490-ish) is
 painful.

This would be really tedious, especially with my dialup internet connection. Michael
Nov 27 2006
parent reply Steve Horne <stephenwantshornenospam100 aol.com> writes:
On Mon, 27 Nov 2006 20:04:10 +0100, Michael Butscher
<mbutscher gmx.de> wrote:

Steve Horne wrote:

 Maybe Python is doing the (1) thing, but that leaves me wondering how
 come my existing code is working.

Before closures were introduced in Python (about 2.2 or so), it was a common idiom to write: lambda a=a: ... to access an outer variable a. Maybe you are using something like that.

No. I used to, but it was a big relief when I didn't need to any more. I'm not so sure now that I change variables much after using them like this. -- Remove 'wants' and 'nospam' from e-mail.
Nov 27 2006
parent Michael Butscher <mbutscher gmx.de> writes:
Steve Horne wrote:
 On Mon, 27 Nov 2006 20:04:10 +0100, Michael Butscher
 <mbutscher gmx.de> wrote:
 
Steve Horne wrote:

 Maybe Python is doing the (1) thing, but that leaves me wondering how
 come my existing code is working.

Before closures were introduced in Python (about 2.2 or so), it was a common idiom to write: lambda a=a: ... to access an outer variable a. Maybe you are using something like that.

No. I used to, but it was a big relief when I didn't need to any more. I'm not so sure now that I change variables much after using them like this.

Me too :-) It seems that full-blown closures with live access to outer variables (as long as the outer function exists) are of much rarer need than one might think at first. Michael
Nov 28 2006
prev sibling parent reply David Medlock <noone nowhere.com> writes:
Steve Horne wrote:
 On Sun, 26 Nov 2006 15:28:03 +0100, Michael Butscher
 <mbutscher gmx.de> wrote:
 
 
Steve Horne wrote:

So for instance, in Python (which does use closures)...

a = 5
fn = lambda : a
a = 6
print fn()

The output should be 5, not 6 - the value when the lambda expression
was evaluated.

Have you tried that? With Python 2.5 in an interactive session, I get:
def test():



a = 5 fn = lambda : a a = 6 print fn()
test()



6

No, I didn't test, and now I'm a bit embarrassed, and confused. I have tonnes of code that uses lambdas, and I'm sure some depends on this behaviour. Code which is heavily used and which all seems to work. Yet suddenly, I can't get a simple example to work right. All I can say is that something's going on in Python that I don't know about. I've checked my favorite compiler-stuff text (Modern Compiler Design, Dick Grune et al) and theres a section (6.3.5.5 Currying a routine) that seems to agree with my closure definition more-or-less. But this is about currying, not inner functions. In the same book, section 6.3.5.3 is directly relevant (title "Returning a nested routine as a value"). It describes the using-dead-variables issue, but actually suggests keeping the local variables for the outer function in a heap frame rather than on the stack. But... 1 This is the variables for the outer function, not the inner function. You put those variables in the stack frame whether the inner function object is actually created or not, and several inner function objects could be created that all refer to the same stack frame. 2 It doesn't use the term closure to describe this. So basically, I thought I knew what I was talking about, but now I'm not so sure. Maybe Python is doing the (1) thing, but that leaves me wondering how come my existing code is working. Incidentally, Amazon seems to have the full text of the book if you want to check exactly what it says, but stepping through the pages one-by-one to get to the relevant section (around page 490-ish) is painful.

In my understanding, closures are like functions which carry state along with them. Like objects but with only a single method: opCall(). in Lua syntax: function make_adder() local sum = 0; return function(n) sum = sum + n; return sum; end end x = make_adder() print(x(5)) 5 print(x(10)) 15 the function returned is a closure of the environment in make_adder. When the closure carries along the sum value it is called lambda lifting. (sum is called an 'upvalue') Currying simply allows composition of larger functions from smaller (incomplete) ones. In Lua: function f(a,b) return a + b; end to curry f with the value of 1: x = function(b) return f(1 , b); end or more generally: def curry(fn,val) return function(b) return fn(val,b) end end Coroutines are interesting as they also exhibit the same state-capture as closures. Here is an equivalent example in Lua: function adder(sum) while(true) do sum = sum + coroutine.yield(sum) end end function make_adder() return coroutine.create(adder); end a = make_adder() ok,x = coroutine.resume( a, 5 ) print( x ) ok, x = coroutine.resume( a, 10 ) print( x ) Off the top of my head, so quite probably errors here. I ran my code in Lua 5.1, though. -DavidM
Nov 27 2006
parent reply Michael Butscher <mbutscher gmx.de> writes:
David Medlock wrote:

[What are closures?]
 In my understanding, closures are like functions which carry state along 
 with them.  Like objects but with only a single method: opCall().
 
 in Lua syntax:
 
 function make_adder()
    local sum = 0;
    return function(n) sum = sum + n; return sum; end
 end

What happens while the outer function is "alive" yet? E.g. something like (I don't know Lua, therefore I guessed syntax): function test() local sum = 0; local x = function(n) sum = sum + n; return sum; end sum = 5; print(x(5)); end Does this print 5 or 10? Michael
Nov 28 2006
parent David Medlock <noone nowhere.com> writes:
Michael Butscher wrote:
 David Medlock wrote:
 
 [What are closures?]
 
In my understanding, closures are like functions which carry state along 
with them.  Like objects but with only a single method: opCall().

in Lua syntax:

function make_adder()
   local sum = 0;
   return function(n) sum = sum + n; return sum; end
end

What happens while the outer function is "alive" yet? E.g. something like (I don't know Lua, therefore I guessed syntax):

As a testament to Lua, you guessed correctly... Javascript 1.5 syntax is very similar.
 
 function test()
    local sum = 0;
    local x = function(n) sum = sum + n; return sum; end
    sum = 5;
    print(x(5));
 end
 
 
 Does this print 5 or 10?
 
 
 
 Michael

When a stack frame is collected, upvalues(sum) are copied into the closure x. Sum will outlive the function test(), but won't be copied until you leave. I ran this in Lua 5.1:
 test()

Obviously you need your copy semantics defined well to use them. This is why several functional languages make variables copy-on-write. For python this would be tuples, you can only make a new one not overwrite the old one. -DavidM
Nov 28 2006
prev sibling next sibling parent Marcio <mqmnews321 sglebs.com> writes:
Michael Butscher wrote:
 Hi,
 
 this is yet another idea how to return delegates from a function 
 without destroying the context (which could be on the stack).

Related: the way #Smalltalk implements blocks on .NET: http://www.refactory.com/Software/SharpSmalltalk/Implementation.html marcio
Nov 25 2006
prev sibling parent "Andrey Khropov" <andkhropov_nosp m_mtu-net.ru> writes:
Walter expressed his opinion in this thread:

http://www.digitalmars.com/d/archives/digitalmars/D/40600.html

-- 
AKhropov
Nov 25 2006