View mode: basic / threaded / horizontal-split · Log in · Help
November 26, 2002
Function types
Hi,

   In the last months people said lots of things about function types and
closures. While function pointers and delegates are nice for many-purposes,
a generic closure notation can be more concise and useful than both
concepts. Also any library designer needs to cover both cases, since none is
a super-type of the other. Every function written using a function pointer
parameter needs to be rewritten using a delegate parameter, and vice-versa.
   Later posts metioned a syntax using the 'anon' identifier, which could
be replaced by any keyword (fun, like many functional languages, maybe?) to
define function literals. The most powerful, and most important problem, of
closures is the binding of free variables. So a compose function would be
written as:


template Functional(T,U,V) {
   T fun(U) compose(T fun(V) f, V fun(U) g) {
       return T fun(U u) {return f(g(u))};
   }
}


   In this example the free variables f and g are referenced in the body of
the closure, and can outlive compose caller's life as in:


bit not(bit condition) {
   return !condition;
}
bit isSpace(char c) {
   return c == ' ';
}
bit fun(char) aFunctor() {
   return instance Functional(bit, char, bit).compose(not, isSpace);
}


   This leads to the problem of update of variables in closures. If the
referenced variable runs out of scope but the closure still lives. It's like
the dangling pointer problem. There's a simple solution to it: disallow
assignments in function literals. So the problem of:


import deimos.arrays;
int main()

   instance TArrays(int) arrays;
   const int[] numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
   int sum = 0;
   arrays.foreach(numbers, void fun(int i) {sum += i;});
   printf("Sum is %d.", sum);
   return 0;
}


would disappear, because either the closure should be transformed in a
function or class member, or another, safer, idiom should be used
(functional semantics with high-order functions, HOF, comes to mind).

import deimos.arrays;
private int sum = 0;
private void add(int i) {
   sum += i;
}
int main()

   instance TArrays(int) arrays;
   const int[] numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
   arrays.foreach(numbers, &add);
   printf("Sum is %d.", sum);
   return 0;
}

import deimos.arrays;
private class Adder {
   public int sum = 0;
   public void add(int i) {
       sum += i;
   }
}
int main()

   instance TArrays(int) arrays;
   const int[] numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
   Adder adder = new Adder();
   arrays.foreach(numbers, &adder.add);
   printf("Sum is %d.", adder.sum);
   return 0;
}

import deimos.arrays;
int main()

   instance TArrays(int) arrays;
   const int[] numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
   int sum = arrays.foldl(numbers, 0, int fun(int x, int y) {return x +
y;});
   printf("Sum is %d.", sum);
   return 0;
}


   The third option, using HOF, is the less verbose of all, and simpler
(once you grasp the foldl semantics). A simples syntax (a la Haskell or ML)
would be better, so instead of int fun(int x, int y) {return x + y;} we
could have (fun x y -> x + y;) with type inference based on context and all.
But it's not a requisite.
   With a single function literal, closure semantics and funtion type
definition, we could define type conversion between function types, so a
more specific function can be passed to a function requiring a more generic
one (today it's not possible). The following example may illustrate this:

class Complex {}
class Real : Complex {}
class Integer : Real {}

void printResult(Complex fun(Integer, Real) function, Integer a, Integer b)
{
   Complex c = function(a,b);
   printf("%.*s == function(%.*s, %.*s)", c.toString(), a.toString(),
b.toString());
}
int main() {
   Integer x = new Integer(0);
   Integer y = new Integer(10);
   printResult(Complex fun(Integer a, Real b) {return a + b;}, x, y);
/* valid because it's an invariant match
*/
   printResult(Complex fun(Real a, Real b) {return a + b;}, x, y);
/* valid because anonimous function's parameter types are super-types
  of expected types, being contravariantly redefined
*/
   printResult(Integer fun(Integer a, Real b) {return a + b;}, x, y);
/* valid because anonimous function's return type is a sub-type
  of expected type, being covariantly redefined
*/
   return 0;
}


   This function subtyping rule is the same from functional languages and
allows more code reuse (in polymorphic parameters).

   Best regards,
   Daniel Yokomiso.

"If life was fair, Elvis would be alive and all the impersonators would be
dead."
- Johnny Carson
November 26, 2002
Re: Function types
Tim Wrentsh also argued for closures with the extended lifetime. I agree
it's a great idea, but am not sure how to implement it.

"Daniel Yokomiso" <daniel_yokomiso@yahoo.com.br> wrote in message
news:arumnp$1i2g$2@digitaldaemon.com...
> Hi,
>
>     In the last months people said lots of things about function types and
> closures. While function pointers and delegates are nice for
many-purposes,
> a generic closure notation can be more concise and useful than both
> concepts. Also any library designer needs to cover both cases, since none
is
> a super-type of the other. Every function written using a function pointer
> parameter needs to be rewritten using a delegate parameter, and
vice-versa.
>     Later posts metioned a syntax using the 'anon' identifier, which could
> be replaced by any keyword (fun, like many functional languages, maybe?)
to
> define function literals. The most powerful, and most important problem,
of
> closures is the binding of free variables. So a compose function would be
> written as:
>
>
> template Functional(T,U,V) {
>     T fun(U) compose(T fun(V) f, V fun(U) g) {
>         return T fun(U u) {return f(g(u))};
>     }
> }
>
>
>     In this example the free variables f and g are referenced in the body
of
> the closure, and can outlive compose caller's life as in:
>
>
> bit not(bit condition) {
>     return !condition;
> }
> bit isSpace(char c) {
>     return c == ' ';
> }
> bit fun(char) aFunctor() {
>     return instance Functional(bit, char, bit).compose(not, isSpace);
> }
>
>
>     This leads to the problem of update of variables in closures. If the
> referenced variable runs out of scope but the closure still lives. It's
like
> the dangling pointer problem. There's a simple solution to it: disallow
> assignments in function literals. So the problem of:
>
>
> import deimos.arrays;
> int main()
>
>     instance TArrays(int) arrays;
>     const int[] numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
>     int sum = 0;
>     arrays.foreach(numbers, void fun(int i) {sum += i;});
>     printf("Sum is %d.", sum);
>     return 0;
> }
>
>
> would disappear, because either the closure should be transformed in a
> function or class member, or another, safer, idiom should be used
> (functional semantics with high-order functions, HOF, comes to mind).
>
> import deimos.arrays;
> private int sum = 0;
> private void add(int i) {
>     sum += i;
> }
> int main()
>
>     instance TArrays(int) arrays;
>     const int[] numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
>     arrays.foreach(numbers, &add);
>     printf("Sum is %d.", sum);
>     return 0;
> }
>
> import deimos.arrays;
> private class Adder {
>     public int sum = 0;
>     public void add(int i) {
>         sum += i;
>     }
> }
> int main()
>
>     instance TArrays(int) arrays;
>     const int[] numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
>     Adder adder = new Adder();
>     arrays.foreach(numbers, &adder.add);
>     printf("Sum is %d.", adder.sum);
>     return 0;
> }
>
> import deimos.arrays;
> int main()
>
>     instance TArrays(int) arrays;
>     const int[] numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
>     int sum = arrays.foldl(numbers, 0, int fun(int x, int y) {return x +
> y;});
>     printf("Sum is %d.", sum);
>     return 0;
> }
>
>
>     The third option, using HOF, is the less verbose of all, and simpler
> (once you grasp the foldl semantics). A simples syntax (a la Haskell or
ML)
> would be better, so instead of int fun(int x, int y) {return x + y;} we
> could have (fun x y -> x + y;) with type inference based on context and
all.
> But it's not a requisite.
>     With a single function literal, closure semantics and funtion type
> definition, we could define type conversion between function types, so a
> more specific function can be passed to a function requiring a more
generic
> one (today it's not possible). The following example may illustrate this:
>
> class Complex {}
> class Real : Complex {}
> class Integer : Real {}
>
> void printResult(Complex fun(Integer, Real) function, Integer a, Integer
b)
> {
>     Complex c = function(a,b);
>     printf("%.*s == function(%.*s, %.*s)", c.toString(), a.toString(),
> b.toString());
> }
> int main() {
>     Integer x = new Integer(0);
>     Integer y = new Integer(10);
>     printResult(Complex fun(Integer a, Real b) {return a + b;}, x, y);
> /* valid because it's an invariant match
>  */
>     printResult(Complex fun(Real a, Real b) {return a + b;}, x, y);
> /* valid because anonimous function's parameter types are super-types
>    of expected types, being contravariantly redefined
>  */
>     printResult(Integer fun(Integer a, Real b) {return a + b;}, x, y);
> /* valid because anonimous function's return type is a sub-type
>    of expected type, being covariantly redefined
>  */
>     return 0;
> }
>
>
>     This function subtyping rule is the same from functional languages and
> allows more code reuse (in polymorphic parameters).
>
>     Best regards,
>     Daniel Yokomiso.
>
> "If life was fair, Elvis would be alive and all the impersonators would be
> dead."
> - Johnny Carson
>
>
>
>
November 27, 2002
Re: Function types
Maybe a simple struct containing the free variables and the function pointer
of the code? Java compile annonimous inner classes in this way, like:


void doStuff(final int x, final float f) {
   numbers.forEach(new Operation() {
       void each(Object o) {
           Integer i = (Integer) o;
           System.out.println(i.intValue() + x * f);
       }
   });
}


IIRC it create a class with members x and f and the method each. D could
have it the same way. Sather has closures, and functional languages have
too. Most of them have a free (as in freedom) compiler, some target C as
intermediate language, so I think it's an efficient and safe way to
implement it.


"Walter" <walter@digitalmars.com> escreveu na mensagem
news:as1108$15fo$4@digitaldaemon.com...
> Tim Wrentsh also argued for closures with the extended lifetime. I agree
> it's a great idea, but am not sure how to implement it.
>
> "Daniel Yokomiso" <daniel_yokomiso@yahoo.com.br> wrote in message
> news:arumnp$1i2g$2@digitaldaemon.com...
> > Hi,
> >
> >     In the last months people said lots of things about function types
and
> > closures. While function pointers and delegates are nice for
> many-purposes,
> > a generic closure notation can be more concise and useful than both
> > concepts. Also any library designer needs to cover both cases, since
none
> is
> > a super-type of the other. Every function written using a function
pointer
> > parameter needs to be rewritten using a delegate parameter, and
> vice-versa.
> >     Later posts metioned a syntax using the 'anon' identifier, which
could
> > be replaced by any keyword (fun, like many functional languages, maybe?)
> to
> > define function literals. The most powerful, and most important problem,
> of
> > closures is the binding of free variables. So a compose function would
be
> > written as:
> >
> >
> > template Functional(T,U,V) {
> >     T fun(U) compose(T fun(V) f, V fun(U) g) {
> >         return T fun(U u) {return f(g(u))};
> >     }
> > }
> >
> >
> >     In this example the free variables f and g are referenced in the
body
> of
> > the closure, and can outlive compose caller's life as in:
> >
> >
> > bit not(bit condition) {
> >     return !condition;
> > }
> > bit isSpace(char c) {
> >     return c == ' ';
> > }
> > bit fun(char) aFunctor() {
> >     return instance Functional(bit, char, bit).compose(not, isSpace);
> > }
> >
> >
> >     This leads to the problem of update of variables in closures. If the
> > referenced variable runs out of scope but the closure still lives. It's
> like
> > the dangling pointer problem. There's a simple solution to it: disallow
> > assignments in function literals. So the problem of:
> >
> >
> > import deimos.arrays;
> > int main()
> >
> >     instance TArrays(int) arrays;
> >     const int[] numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
> >     int sum = 0;
> >     arrays.foreach(numbers, void fun(int i) {sum += i;});
> >     printf("Sum is %d.", sum);
> >     return 0;
> > }
> >
> >
> > would disappear, because either the closure should be transformed in a
> > function or class member, or another, safer, idiom should be used
> > (functional semantics with high-order functions, HOF, comes to mind).
> >
> > import deimos.arrays;
> > private int sum = 0;
> > private void add(int i) {
> >     sum += i;
> > }
> > int main()
> >
> >     instance TArrays(int) arrays;
> >     const int[] numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
> >     arrays.foreach(numbers, &add);
> >     printf("Sum is %d.", sum);
> >     return 0;
> > }
> >
> > import deimos.arrays;
> > private class Adder {
> >     public int sum = 0;
> >     public void add(int i) {
> >         sum += i;
> >     }
> > }
> > int main()
> >
> >     instance TArrays(int) arrays;
> >     const int[] numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
> >     Adder adder = new Adder();
> >     arrays.foreach(numbers, &adder.add);
> >     printf("Sum is %d.", adder.sum);
> >     return 0;
> > }
> >
> > import deimos.arrays;
> > int main()
> >
> >     instance TArrays(int) arrays;
> >     const int[] numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
> >     int sum = arrays.foldl(numbers, 0, int fun(int x, int y) {return x +
> > y;});
> >     printf("Sum is %d.", sum);
> >     return 0;
> > }
> >
> >
> >     The third option, using HOF, is the less verbose of all, and simpler
> > (once you grasp the foldl semantics). A simples syntax (a la Haskell or
> ML)
> > would be better, so instead of int fun(int x, int y) {return x + y;} we
> > could have (fun x y -> x + y;) with type inference based on context and
> all.
> > But it's not a requisite.
> >     With a single function literal, closure semantics and funtion type
> > definition, we could define type conversion between function types, so a
> > more specific function can be passed to a function requiring a more
> generic
> > one (today it's not possible). The following example may illustrate
this:
> >
> > class Complex {}
> > class Real : Complex {}
> > class Integer : Real {}
> >
> > void printResult(Complex fun(Integer, Real) function, Integer a, Integer
> b)
> > {
> >     Complex c = function(a,b);
> >     printf("%.*s == function(%.*s, %.*s)", c.toString(), a.toString(),
> > b.toString());
> > }
> > int main() {
> >     Integer x = new Integer(0);
> >     Integer y = new Integer(10);
> >     printResult(Complex fun(Integer a, Real b) {return a + b;}, x, y);
> > /* valid because it's an invariant match
> >  */
> >     printResult(Complex fun(Real a, Real b) {return a + b;}, x, y);
> > /* valid because anonimous function's parameter types are super-types
> >    of expected types, being contravariantly redefined
> >  */
> >     printResult(Integer fun(Integer a, Real b) {return a + b;}, x, y);
> > /* valid because anonimous function's return type is a sub-type
> >    of expected type, being covariantly redefined
> >  */
> >     return 0;
> > }
> >
> >
> >     This function subtyping rule is the same from functional languages
and
> > allows more code reuse (in polymorphic parameters).
> >
> >     Best regards,
> >     Daniel Yokomiso.
> >
> > "If life was fair, Elvis would be alive and all the impersonators would
be
> > dead."
> > - Johnny Carson
> >
> >
> >
> >
>
>
Top | Discussion index | About this forum | D home