www.digitalmars.com         C & C++   DMDScript  

D - Function types

reply "Daniel Yokomiso" <daniel_yokomiso yahoo.com.br> writes:
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
Nov 25 2002
parent reply "Walter" <walter digitalmars.com> writes:
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
Nov 26 2002
parent "Daniel Yokomiso" <daniel_yokomiso yahoo.com.br> writes:
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
Nov 26 2002