Standard Generic Delegate Types, Part Two

  • Artykuł

Last time I asked whether there were examples of delegate types which could be declared with the traditional delegate type declaration syntax that could not be declared with the generic syntax, and Alois Kraus came up with a number of examples. This syntax does not support definition of void delegates, delegates with out or ref parameters, delegates with parameter arrays, generic delegates, delegates which have unsafe parameter or return types, and delegates declarations with attributes on the parameters.

However, there is one other difference between the traditional and generic declaration forms that no one mentioned: the traditional syntax adds a new symbol to the scope, and that symbol can be used in a recursive definition. The generic syntax does not add a new symbol to the scope, so you cannot define a recursively defined delegate type with it.

Consider, for example, the "purest" possible delegate type -- a function that takes a function and returns a function, where both the argument and the return are themselves functions that take functions and return functions. Such a function is called a combinator. That is:

delegate D D(D d);

Using the new lambda syntax, you could concisely define all kinds of combinators:

D I = x=>x
D M = x=>x(x);
D K = x=>y=>x;
D L = x=>y=>x(y(y));
D S = x=>y=>z=>(x(z(y(z))));
D C = a=>b=>c=>a(c)(b);
D B = a=>b=>c=>a(c(b));

Those of you with a background in combinatory logic will certainly recognize all of these combinators. They're of considerable theoretical interest, but not much practical use in C#. (I might discuss some of the properties of these combinators in a later posting, but if you're interested this fascinating subject, I recommend reading Raymond Smullyan's delightful book of combinatory logic puzzles "To Mock A Mockingbird".)

There's no way to define a delegate signature for a combinator using only the generic syntax because it goes into an infinite regress immediately. Neat, eh?

Comments

  • Anonymous
    June 25, 2006
    I do not have a background in combinatory logic necessary to recognize all of these combinators, but nevertheless I'm quite interested in the topic.
    http://en.wikipedia.org/wiki/Combinator defines the combinators I, K, S, B and C.
    What are the other combinators that you mentioned, M and L?
  • Anonymous
    June 25, 2006
    M has a number of interesting properties involving fixed point combinators.  

    For example, if you have a set of combinators such that the composition of any two members of the set is in the set, and M is in the set, then every combinator in the set has a fixed point.  

    By "composes" I mean, if you have two combinators A and B then C composes A with B if for every x, C(x) = A(B(x)).

    By every combinator having a "fixed point" I mean that for any A in the set there exists a B such that A(B) = B.  

    Proof: Pick any A, let C be the combinator in the set which composes A with M, let B = C(C).  C(x) = A(M(x)), so B = C(C) = A(M(C)) = A(C(C)) = A(B), done.

    If L is in the set then we can get there even faster, since L(A) returns the combinator that composes A with M!

    There are a variety of important results in combinatory logic which involve fixed points, so L tends to come up in those contexts.
  • Anonymous
    July 04, 2006
    You write that we can't use lambda expressions for void delegates, but we can do it using a statement body like this:

    delegate void Void();
    Void v = () => { Console.Write("I'm void"); return; };
  • Anonymous
    July 04, 2006
    Of course, return is not needed in my example :-)
  • Anonymous
    July 05, 2006
    I never saild that you can't use lambda expressions for void delegates!  I said that you can't declare a void delegate type with the Func<S, T> syntax.  Func<int, void> is not a legal declaration.
  • Anonymous
    September 25, 2010
    I fail to see the use of the delegate you've defined here, but I can think of one that's actually "useful", or more accurately can be used. The Y combinator would be defined like this: private delegate Func<In, Out> YCombinator<In, Out>(YCombinator<In, Out> combinator); public static Func<In, Out> Y<In, Out>(Func<Func<In, Out>, Func<In, Out>> f) { YCombinator<In, Out> comb = f2 => f(x => f2(f2)(x)); return comb(comb); } Then its use would be something like this public static readonly Func<int, int> factorial = Y<int, int>( f => x => x > 1 ? x * f(x-1) : 1; ); public static readonly Func<int, int> fib = Y<int, int>( f => x => x > 1 ? f(x-1) + f(x-2) : x; ); This sort of thing is useful for anonymous recursive functions. I can think of a few cases I've wanted to write recursive anonymous functions, but couldn't. Reader exercise: Why are we returning f(x => f2(f2)(x)) from comb, and not f(f2(f2))?