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():






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

	

 test()






6



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():






	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.

-- 
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()


10

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