Function minimization and random numbers

[Marc Gravell]

C#'s type system makes the distinction, not me.

minor point, but surely the CLR spec defines the type system, not the
language

That is not how F# supports closures.

OK, I'm *really, really* struggling to see the difference, and I am
genuinely interested (heck, I went to the F# lectures at TechEd...);
can you please explain to me what the F# closures do that isn't easily
achievable in C#. Your point about having to manually translate simply
doesn't work for me, since naming a method to use as a Func [etc]
doesn't strike me as odiously manual; of course a lambda is just as
easy and probably closer to what we are talking about...

I think there is an understanding gap here, and I would truly love to
understand what I am not getting; can you try one more time to explain
what C# 3 doesn't do here?

Marc

 

[Jon Skeet [C# MVP]]

C#'s type system makes the distinction, not me.

Well, .NET's type system makes the distinction, allowing conversions
between them.

However, that seems irrelevant in terms of the question of whether C#
lacks closures. You claim that it does, and I'll ask again: please
provide some widely accepted definition of "closure" which C# doesn't
satisfy.

That is why you must convert a member into a delegate manually in C# when,
in fact, they are both just functions. There's a whole MSDN help page
devoted to this no-op.

What exactly do you mean by "manually"? Do you mean there has to be an
appropriate delegate type to convert to? That's certainly true. I don't
see the issue though - unless you want to do away with static type
safety, there has to be something available to encapsulate the
signature of the function.

Now, you could well want to do away with the static type safety -
Groovy supports overloaded method groups as closures, where the
appropriate method to actually call is determined at execution time,
for example. There are advantages and disadvantages to that - but I
haven't seen anything in a definition of closures which *requires* a
dynamic interface.

Then you are retrofitting language features onto Algol with no regard for
what makes them useful.

Yeah, right. Of course. Anonymous methods and lambda expressions were
added with no thought whatsoever. Get real.

Provided you just want a list of checkboxes of
language features, that's fine, but if you want the features to be useful
then you're going to have to think a lot more about how they interact.

Are you claiming that the C# support for closures is useless? That
would rule out most of LINQ to start with...

Avoid closures if you want to call your F# libraries from C#.

So has F# eschewed the standard .NET use of delegates as effectively
function pointers? If F# really doesn't allow the use of what *the
whole of the rest of .NET* treats as functions to be treated as
functions, that sounds like F#'s fault rather than C#'s. However, I
seem to remember that actually you *can* use delegates in F# perfectly
easily. I'd check with Robert's book, but it's at work at the moment.

That is not how F# supports closures.

Consider a language that support integers but imposes a compile time
distinction between even and odd integers for no logical reason. If that
was the only language you knew, would you back it to the hilt because,
technically, you can work around the type system to use all integers?

Perhaps you'd deign to explain to us mere peasants just why F#'s
support of closures is so wonderful as to make C#'s support appear to
be useless and to even count as a lack of support in your (previously
stated) view.

 

[Jon Harrop]

minor point, but surely the CLR spec defines the type system, not the
language

If that were true then F# would suffer the same fate as C# but it doesn't.
Indeed, this is a Turing argument: you can wrap anything up in the CLR so
it doesn't actually impose anything on your type system.

That is not how F# supports closures.

OK, I'm *really, really* struggling to see the difference, and I am
genuinely interested (heck, I went to the F# lectures at TechEd...);
can you please explain to me what the F# closures do that isn't easily
achievable in C#. Your point about having to manually translate simply
doesn't work for me, since naming a method to use as a Func [etc]
doesn't strike me as odiously manual; of course a lambda is just as
easy and probably closer to what we are talking about...

No. My point is that F# requires no code whatsoever to do the same thing. No
lambda, nothing. You look at a member invocation:

foo.Bar(3)

and say "I want that Bar member as a closure" and you just write:

foo.Bar

to get it. That's it. All done. That is a functional value. You can't even
tell that it came from a member rather than a delegate.

However, that doesn't express just how important it is to remove this
artificial distinction. Until you do that, you're delegates will only ever
be second-class closures because you cannot manipulate all functions in the
same way: you need to know how the function was defined.

 

[Jon Harrop]

Well, .NET's type system makes the distinction, allowing conversions
between them.
Exactly.

However, that seems irrelevant in terms of the question of whether C#
lacks closures. You claim that it does, and I'll ask again: please
provide some widely accepted definition of "closure" which C# doesn't
satisfy.

Delegates are second class constructs, incompatible with other kinds of
functions (members) due to the problem you just described.

What exactly do you mean by "manually"?

The programmer has to do something: the task is not automated by the
compiler.

Do you mean there has to be an
appropriate delegate type to convert to? That's certainly true. I don't
see the issue though - unless you want to do away with static type
safety, there has to be something available to encapsulate the
signature of the function.

You only need a single generic function type:

'a -> 'b

There is no loss of static type safety.

Now, you could well want to do away with the static type safety -

I want a more expressive type system that offers more static type safety.

Groovy supports overloaded method groups as closures, where the
appropriate method to actually call is determined at execution time,
for example. There are advantages and disadvantages to that - but I
haven't seen anything in a definition of closures which *requires* a
dynamic interface.

There are lots of statically-typed functional programming languages: OCaml,
SML, Haskell, F#.

Anonymous methods and lambda expressions were added with no thought
whatsoever.

On the contrary, Microsoft have put a lot of thought into their language
design but it culminated in F# rather than delegates.

Are you claiming that the C# support for closures is useless? That
would rule out most of LINQ to start with...

Relegating functions to second-class citizens makes functional programming
unnecessarily tedious.

So has F# eschewed the standard .NET use of delegates as effectively
function pointers? If F# really doesn't allow the use of what *the
whole of the rest of .NET* treats as functions to be treated as
functions, that sounds like F#'s fault rather than C#'s. However, I
seem to remember that actually you *can* use delegates in F# perfectly
easily. I'd check with Robert's book, but it's at work at the moment.

F# programs can define and use delegates but F#'s closures are not
delegates.

Perhaps you'd deign to explain to us mere peasants just why F#'s
support of closures is so wonderful as to make C#'s support appear to
be useless and to even count as a lack of support in your (previously
stated) view.

Look at parser combinators, for example.

 

[Jon Skeet [C# MVP]]

No. My point is that F# requires no code whatsoever to do the same thing. No
lambda, nothing. You look at a member invocation:

foo.Bar(3)

and say "I want that Bar member as a closure" and you just write:

foo.Bar

You mean like this C# code:

using System;

class Test
{
static void Main()
{
Test foo = new Test();

// Note this line!
CallFunction(foo.Bar);
}

static void CallFunction(Action<int> func)
{
func(5);
}

void Bar(int i)
{
Console.WriteLine(i);
}
}

to get it. That's it. All done. That is a functional value. You can't even
tell that it came from a member rather than a delegate.

In this case CallFunction doesn't know or care that it's been called
with foo.Bar instead of as:

CallFunction(x => Console.WriteLine(x));

However, that doesn't express just how important it is to remove this
artificial distinction. Until you do that, you're delegates will only ever
be second-class closures because you cannot manipulate all functions in the
same way: you need to know how the function was defined.

I don't see why - tell me why CallFunction (above) has to care...

 

[Jon Skeet [C# MVP]]

Delegates are second class constructs, incompatible with other kinds of
functions (members) due to the problem you just described.

What "problem"? I don't remember describing a problem.

The programmer has to do something: the task is not automated by the
compiler.

The compiler performs implicit conversions from method groups and
anonymous functions to delegates.

You only need a single generic function type:

'a -> 'b

There is no loss of static type safety.

You only need a single generic function if you only want a single
parameter. How can you tell the difference between a function taking
two integers and a function taking two strings in F#? Or do functions
only ever take a single parameter which then has to be a tuple if it
needs more than one piece of information? That sounds to me like it's
just pushing the problem down to defining the tuple.

I want a more expressive type system that offers more static type safety.


There are lots of statically-typed functional programming languages: OCaml,
SML, Haskell, F#.

Okay, so if it's not static typing that's the problem, I'll ask again
what you actually can't do with C#. You haven't given a straight answer

On the contrary, Microsoft have put a lot of thought into their language
design but it culminated in F# rather than delegates.

You know perfectly well I was referring to C# - you've just ducked the
question instead of admitting that your previous post was mere
hyperbole.

(You'd increase your credibility by also admitting that C# really
*does* support closures and your claim that it doesn't was also just
hyperbole.)

Relegating functions to second-class citizens makes functional programming
unnecessarily tedious.

While it's true that I wouldn't use C# if I wanted a language which is
primarily designed for functional programming, C# 3 works very well as
a language which lets you use a functional style when you want to and
an OO/imperative style where that's more appropriate.

F# programs can define and use delegates but F#'s closures are not
delegates.

So F# can't pass a closure to a method which takes a delegate
parameter? That's a pity, given LINQ etc.

Look at parser combinators, for example.

No, you forget - we're stupid people, remember? Poor luddites forced to
work with C#. We'll need more than a buzzword phrase.

Of course, a quick bit of googling turns up a blog entry on how to
write/use monadic parser combinators in C# 3:

http://blogs.msdn.com/lukeh/archive/2007/08/19/monadic-parser-
combinators-using-c-3-0.aspx

As Luke says, it's inefficient etc - but doable.

However, the important thing in my view is that very few developers are
actually likely to need to write a parser. Maybe you do, and that's
fine - you may well be better off with F#. Now, perhaps you'll come up
with an example which is more widely applicable.

 

[Marc Gravell]

and say "I want that Bar member as a closure" and you just write:

foo.Bar
That's it. All done.

Well, presumably you write *something* else (i.e. to store/use it) -
and C# 2 does exactly the same thing;

[sig] func = foo.Bar; // stored as an invokable function
SomeMethod(foo.Bar); // passed downstream as an invokable function

(also "All done").

As long as the number of arguments is known (otherwise how would you
ever use it), the above can happily be combined with generics and type
inference such that the signature is type agnostic. C# 3 improves this
by extending the type inference rules and adding lambdas for improved
ability to express a "function" without worrying about methods; yes
under the bonnet a lambda (in delegate form) is compiled to a member,
but I've not once had to worry about any such distinction - it is just
an invokable unit of code...

However, that doesn't express just how important it is to remove
this
artificial distinction.

I really don't see what you are getting at. You talk about odd and
even; fine: *show me* what distinction/limitation the above has?

Until you do that, you're delegates will only ever
be second-class closures because you cannot manipulate all functions
in the
same way: you need to know how the function was defined.

I simply don't understand what you mean. You keep using the same
phrases to justify the difference, but you haven't actually
demonstrated anything that is not trivial is C#. Maybe there are
better examples?

Marc

 

[Jon Harrop]

Well, presumably you write *something* else (i.e. to store/use it) -

Function application is far more common that binding a functional value to a
variable in functional programming. This is why functional languages have
such concise syntax for function application (including partial
application):

f x

and C# 2 does exactly the same thing;

[sig] func = foo.Bar; // stored as an invokable function
SomeMethod(foo.Bar); // passed downstream as an invokable function

Should that be "SomeMethod(func)" here?

(also "All done").

For a more useful example, try writing a complete C# implementation of the
higher-order curried "nest" combinator:

# let rec nest n f x = if n=0 then x else nest (n-1) f (f x);;

As long as the number of arguments is known (otherwise how would you
ever use it),

Or, if you have tuples as F# does, functions only ever need 1 argument. This
also serves to make things easier.

the above can happily be combined with generics and type
inference such that the signature is type agnostic.

Actually I am unable to combine these examples with generics. The C#
compiler keeps barfing with the error:

'f' is a 'variable' but is used like a 'method'

If functions were first class in C# that error would not exist. Perhaps this
is fixed in C# 3 but I haven't been able to get that working here yet. I'll
try again...

I simply don't understand what you mean. You keep using the same
phrases to justify the difference, but you haven't actually
demonstrated anything that is not trivial is C#. Maybe there are
better examples?

I believe you will find that nest example is "not trivial in C#" but I can
provide plenty more examples if you like (they are likely to be more
complicated but also more practically relevant). Lexers and parsers are
good ones. I'm sure I can find plenty more in our codebases.

 

[Marc Gravell]

  f x

And that means?

Should that be "SomeMethod(func)" here?

No; I was demonstrating 2 different uses; first as storage, and then
(unrelated) passing a function as a parameter. Of course it *could*
have used SomeMethod(func) - but I was trying to illustrate that you
can just pass the function directly, regarless of whether it is a
member or a local variable.

try writing a complete C# implementation of the higher-order curried "nest" combinator:
# let rec nest n f x = if n=0 then x else nest (n-1) f (f x);;
val nest : int -> ('a -> 'a) -> 'a -> 'a = <fun>

I'd certainly take a look if you tell me what it does in English;
pretend I don't speak ML...

Or, if you have tuples as F# does, functions only ever need 1 argument. This
also serves to make things easier.

I don't think it makes anything much harder or easier; just a
different approach; the same could presumably be achieved with a
generic tuple in C#, or at worst case an array. Out of interest, how
much do you know about the *type* of tuple? Is it defined that it
takes "a tuple of 2 ints, a string and a cat"?

'f' is a 'variable' but is used like a 'method'

It needs to know that f is a delegate [read: function] - if you post
some non-working (but indicative of what you are trying to look at )
C# I'll happily take a look.

Marc

 

[Jon Skeet [C# MVP]]

For a more useful example, try writing a complete C# implementation of the
higher-order curried "nest" combinator:

# let rec nest n f x = if n=0 then x else nest (n-1) f (f x);;
val nest : int -> ('a -> 'a) -> 'a -> 'a = <fun>

Okay, well here's a go at it:

Func<int,Func<int,int>,Func<int,int>> nest = null;
nest = ((n,f) => (x => n==0 ? f(x) : nest(n-1,f)(f(x))));


Complete program:

using System;

class Test
{
static void Main()
{
Func<int,Func<int,int>,Func<int,int>> nest = null;
nest = ((n,f) => (x => n==0 ? f(x) : nest(n-1,f)(f(x))));

// Sample use:
Func<int,int> doubler = x => x*2;

Func<int,int> nested = nest(2, doubler);

// nest(2, doubler)(3) = nest(1, doubler)(3*2)
// nest(1, doubler)(6) = nest(0, doubler)(6*2)
// nest(0, doubler)(12) = 12*2
Console.WriteLine(nested(3)); // Prints 24

}
}

Is that what you'd expect to see, or have I missed something?

 

[Jon Harrop]

And that means?

f(x)

In particular:

f x y

means:

(f(x))(y)

No; I was demonstrating 2 different uses; first as storage, and then
(unrelated) passing a function as a parameter. Of course it *could*
have used SomeMethod(func) - but I was trying to illustrate that you
can just pass the function directly, regarless of whether it is a
member or a local variable.

Right, ok.

I'd certainly take a look if you tell me what it does in English;
pretend I don't speak ML...

Oops, sorry.

That "nest" combinator takes an int "n" and returns a function that takes a
polymorphic function "f" and returns a function that takes an argument "x"
for "f" and applies "n" applications of "f" to "n".

For example, "nest 3 f x" gives "f(f(f(x)))".

These kinds of functions have lots of practical applications. In the context
of parsers, a combinator might match a sequence of one or more repeats of a
pattern where the argument "f" is responsible for matching the sub-pattern
(which could be a sequence of repeats itself). In the context of numerical
computing, a combinator might keep iterating (i.e. applying "f") until the
result stops changing. In the context of graphics, the same combinator
might be used to traverse a scene graph with culling, e.g. to accumulate a
result, such as the bound, or to actually render the graphics.

I don't think it makes anything much harder or easier; just a
different approach; the same could presumably be achieved with a
generic tuple in C#, or at worst case an array. Out of interest, how
much do you know about the *type* of tuple? Is it defined that it
takes "a tuple of 2 ints, a string and a cat"?

Exactly, yes. A tuple is the simplest possible product type. A polymorphic
pair is written:

'a * 'b

Note that the two elements of this pair have different types, which is not
true of a 2-element array.

You'll often use monomorphic types (i.e. specific types for 'a or 'b or
both) like:

string * int

So 2-argument C# function that accepts a string and an int is a 1-argument
F# function that accepts a pair. The signature of the whole F# function
might be:

val f : string * int -> unit

This becomes useful when you combine it with destructuring via pattern
matching. So you can write things like:

let f (a, (b, c)) = ((a, b), c)

'f' is a 'variable' but is used like a 'method'

It needs to know that f is a delegate [read: function] - if you post
some non-working (but indicative of what you are trying to look at )
C# I'll happily take a look.

Yes. I think the problem is that I'm treating the explicit types in my C#
code as annotation when they must actually be declarations.

I was writing something like:

B apply<F, A, B>(F f, A a) {
return f(a);
}

Special casing to B is void I can write:

void apply<A>(Action<A> f, A a) {
f(a);
}

and it works.

 

[Jon Harrop]

Okay, well here's a go at it:

Func<int,Func<int,int>,Func<int,int>> nest = null;
nest = ((n,f) => (x => n==0 ? f(x) : nest(n-1,f)(f(x))));

I think the type should be:

Func<int, Func<Func<A, A>, Func<A, A>>>

because the "nest" combinator is curried and the definition maybe:

nest = (n => (f => (x => n==0 ? x : nest(n-1)(f)(f(x)))));

Complete program:

using System;

class Test
{
static void Main()
{
Func<int,Func<int,int>,Func<int,int>> nest = null;
nest = ((n,f) => (x => n==0 ? f(x) : nest(n-1,f)(f(x))));

// Sample use:
Func<int,int> doubler = x => x*2;

Func<int,int> nested = nest(2, doubler);

// nest(2, doubler)(3) = nest(1, doubler)(3*2)
// nest(1, doubler)(6) = nest(0, doubler)(6*2)
// nest(0, doubler)(12) = 12*2
Console.WriteLine(nested(3)); // Prints 24

}
}

Is that what you'd expect to see, or have I missed something?

That is certainly better than I thought possible (is this C# 3 specific?)
but I still have some questions:

.. Is the use of "null" necessary or can it be avoided?

.. Does the C# compile to a tail call?

.. How do you make it generic?

.. Can you apply the C# "nest" combinator without declaring any types, like
this:

nest(5)(x => x*2)(1) // = 2^5 = 32

 

[Jon Skeet [C# MVP]]

I think the type should be:

Func<int, Func<Func<A, A>, Func<A, A>>>

because the "nest" combinator is curried and the definition maybe:

nest = (n => (f => (x => n==0 ? x : nest(n-1)(f)(f(x)))));

but I don't know where to put the generics <A>.

Right - I wasn't sure how far it should be curried. (I also made a
mistake of returning f(x) when n was 0 rather than x.)

The generics can't be done "inline" like that, but can easily be done
with a generic method:

using System;

class Test
{
static Func<Func<A,A>, Func<A,A>> Nest<A> (int n)
{
return f => (x => n==0 ? x : Nest<A>(n-1)(f)(f(x)));
}

static void Main()
{
var nested = Nest<int>(2);

Console.WriteLine (nested(x => x*2)(3));
}
}

Yes, that means using a method call inside the method (although only
within the closure - it doesn't recurse when you call it, of course).
This could be avoided artificially, but it's the most natural way of
doing it.

That is certainly better than I thought possible (is this C# 3 specific?)

The lambda expressions are certainly C# 3 specific. It could probably
have been done with anonymous methods, but it wouldn't have been nearly
as nice.

but I still have some questions:

. Is the use of "null" necessary or can it be avoided?

Unfortunately it's necessary in the original code, for reasons of
definite assignment. The rules for definite assignment could have been
made *much* more complicated to spot this, but it's rarely an issue and
the workaround is simple.

. Does the C# compile to a tail call?

The C# compiler itself doesn't, but some variants of the JIT compiler
do. I seem to remember that the 64 bit JIT does this, but the 32 bit
JIT doesn't.

. How do you make it generic?

See above - although you do need to specify the type when you call the
method. With one fewer level of currying (as per my original) this
could be done by type inference.

. Can you apply the C# "nest" combinator without declaring any types, like
this:

nest(5)(x => x*2)(1) // = 2^5 = 32

Yup. Indeed, to take the above one level further:

int p = Nest<int>(5)(x => x*2)(1);

(And it gets the right answer, too