# Latest version: https://weblogs.asp.net/dixin/lambda-calculus-via-c-1-fundamentals

C# lambda expression is discussed in detail used everywhere in the LINQ via C# series. This post and the following few posts will focus on functions and disregard lambda expression for expression tree. These articles will be a deeper dive about lambda expression and lambda calculus - how it comes, what it does, and why it matters. And - functions and anonymous functions will always be the only primitive.

# About lambda calculus (λ-calculus)

Lambda calculus is a formal system to use functions and function application to express computation. Lambda calculus is Turing complete.

In C#, lambda is a fancy feature introduced in 3.0. Actually it is introduced as early as 1930s by Alonzo Church, the doctoral advisor of Alan Turing. Later Alan Turing showed Turing machines equated the lambda calculus in expressiveness. This series will try to use C# functions to demonstrate how lambda expressions model the computation.

# Closure

All stories can start with a simple concept, closure. Closure has been explained when discussing C# features in a previous chapter. It is actually a general concept that, in lambda calculus, any function can reference a non-local variable,

# Currying and partial application

Looking at this simple function:

```Func<int, int, int> add =
(x, y) => x + y;```

Straightforward. It represents an algorithm to add 2 integers. In C#, it is a function of type Func<int, int, int>.

• The function takes 2 integer parameters as input (on the left side of  =>)
• The function returns the sum of those 2 integers as output (on the right side of =>).

Since C# supports closure and higher-order function, above function can be tweaked a little bit:

```Func<int, Func<int, int>> curriedAdd =
x => new Func<int, int>(y => x + y);```

It  represents an algorithm which eventually still adds 2 integers. The different is:

• The function takes 1 integer parameter as input (on the left side of first  =>)
• The function returns a function as output (on the right side of first =>).
• The returned function takes 1 integer parameter as input (on the left side of second =>)
• The returned function the sum of those 2 integers as output (on the left side of second =>). Here x + y uses closure to reference x, which is out of the returned function (y => x + y).

In C# the returned function’s type declaration, new Func<int, int>(…), can be inferred by compiler. So it can be written cleaner:

```Func<int, Func<int, int>> curriedAdd =
x => y => x + y;```

The add function’s application is also straightforward :

`int result = add(1, 2);`

or just keep the code in lambda style - function should be anonymous without name:

`result = new Func<int, int, int>((x, y) => x + y)(1, 2);`

The second function’s application is different:

```Func<int, int> add1 = curriedAdd(1); // Or: new Func<int, Func<int, int>>(x => y => x + y)(1);
// Now add1 is s closure: y => 1 + y.
result = add1(2);```

So after the function transforming, the function application add(1, 2) becomes curriedAdd(1)(2). This approach, to transform a function with 2 parameters into a sequence of 2 functions where each function has 1 parameter, is called currying. The application of one argument to a curried function, is called partial application.

Similarly, the following function with 3 parameters:

```Func<int, int, int, int> add = (x, y, z) => x + y + z;
int result = add(1, 2, 3);```

can be curried as:

`Func<int, Func<int, Func<int, int>>> curriedAdd = x => y => z => x + y + z;`

and the curried function can be partially applied:

```Func<int, Func<int, int>> add1 = curriedAdd(1); // add1 is a closure: y => z => 1 + y + z
Func<int, int> add3 = add1(2); // add3 is a closure: z => 1 + 2 + z
result = add3(3);
// Or just:
result = curriedAdd(1)(2)(3);```

More generally, any function with N parameters:

`Func<T1, T2, …, TN, TResult> function = (arg1, arg2, …, argN) => result;`

can be curried into a function sequence of N functions, and each function has 1 parameter:

`Func<T1, Func<T2, …, Func<TN, TResult>…>> curriedFunction = arg1 => arg2 => … => argN => result;`

This can be implemented with some Curry() extension methods:

```public static partial class FuncExtensions
{
// from arg => result
// to () => arg => result
public static Func<Func<T, TResult>> Curry<T, TResult>
(this Func<T, TResult> function) =>
() => arg => function(arg);

// from (arg1, arg2) => result
// to arg1 => arg2 => result
public static Func<T1, Func<T2, TResult>> Curry<T1, T2, TResult>
(this Func<T1, T2, TResult> function) =>
arg1 => arg2 => function(arg1, arg2);

// from (arg1, arg2, arg3) => result
// to arg1 => arg2 => arg3 => result
public static Func<T1, Func<T2, Func<T3, TResult>>> Curry<T1, T2, T3, TResult>
(this Func<T1, T2, T3, TResult> function) =>
arg1 => arg2 => arg3 => function(arg1, arg2, arg3);

// from (arg1, arg2, arg3, arg4) => result
// to arg1 => arg2 => arg3 => arg4 => result
public static Func<T1, Func<T2, Func<T3, Func<T4, TResult>>>> Curry<T1, T2, T3, T4, TResult>
(this Func<T1, T2, T3, T4, TResult> function) =>
arg1 => arg2 => arg3 => arg4 => function(arg1, arg2, arg3, arg4);

// ...
}```

With the same idea as currying, we can also partially apply a function with multiple parameters:

```public static partial class FuncExtensions
{
public static Func<TResult> Partial<T, TResult>(
this Func<T, TResult> function, T arg)
{
return () => function(arg);
}

public static Func<T2, TResult> Partial<T1, T2, TResult>(
this Func<T1, T2, TResult> function, T1 arg1)
{
return arg2 => function(arg1, arg2);
}

public static Func<T2, Func<T3, TResult>> Partial<T1, T2, T3, TResult>(
this Func<T1, T2, T3, TResult> function, T1 arg1)
{
return arg2 => arg3 => function(arg1, arg2, arg3);
}

public static Func<T2, Func<T3, Func<T4, TResult>>> Partial<T1, T2, T3, T4, TResult>(
this Func<T1, T2, T3, T4, TResult> function, T1 arg1)
{
return arg2 => arg3 => arg4 => function(arg1, arg2, arg3, arg4);
}

// ...
}```

For example:

```Func<int, int, int, int> add = (x, y, z) => x + y + z;
var add4 = add.Partial(4); // add4 is a closure: y => z => 4 + y + z

int result = add.Partial(1)(2)(3);
// is a short cut of:
result = add.Curry()(1)(2)(3);```

The name "currying" is introduced by Christopher Strachey in 1967. It is the last name of Haskell Curry.

All the later parts of lambda calculus will focus on curried functions (1 parameter function or function sequence). Currying may cause some noise for type inference in C#, which will be demonstrated in a later part of Church pair (2-tuple).

# Uncurry

Just for fun purpose - a sequence of 1 parameter functions can also be uncurried to a function with multiple parameters too:

```public static partial class FuncExtensions
{
// from () => arg => result
// to arg => result
public static Func<T, TResult> Uncurry<T, TResult>
(this Func<Func<T, TResult>> function) =>
arg => function()(arg);

// from arg1 => arg2 => result
// to (arg1, arg2) => result
public static Func<T1, T2, TResult> Uncurry<T1, T2, TResult>
(this Func<T1, Func<T2, TResult>> function) =>
(arg1, arg2) => function(arg1)(arg2);

// from arg1 => arg2 => arg3 => result
// to (arg1, arg2, arg3) => result
public static Func<T1, T2, T3, TResult> Uncurry<T1, T2, T3, TResult>
(this Func<T1, Func<T2, Func<T3, TResult>>> function) =>
(arg1, arg2, arg3) => function(arg1)(arg2)(arg3);

// from arg1 => arg2 => arg3 => arg4 => result
// to (arg1, arg2, arg3, arg4) => result
public static Func<T1, T2, T3, T4, TResult> Uncurry<T1, T2, T3, T4, TResult>
(this Func<T1, Func<T2, Func<T3, Func<T4, TResult>>>> function) =>
(arg1, arg2, arg3, arg4) => function(arg1)(arg2)(arg3)(arg4);

// ...
}```

# => associativity

From above code, the C# lambda operator (=>) is apparently right-associative:

`x => y => x + y`

is identical to:

`x => (y => x + y)`

Or generally:

`Func<T1, Func<T2, …, Func<TN, TResult>…>> curriedFunction = arg1 => arg2 => … => argN => result;`

is identical to:

`Func<T1, Func<T2, …, Func<TN, TResult>…>> curriedFunction = arg1 => (arg2 => … => (argN => result)…);`

This is the same associativity as the type constructor → in typed lambda calculus.

In some functional languages, functions are curried by default, like F#:

`let f1: int -> int -> int = fun x y -> x + y`

fun x y -> … looks like a function definition with multiple parameters, but it is curried as int -> int -> int. This function works similar as:

`let f2: int -> (int -> int) = fun x -> fun y -> x + y`

And this is how to create an uncurried function with multiple parameters in F#:

`let f3: int * int -> int = fun (x, y) -> x + y`

Here multiple parameters are implemented with a tuple of int and int.

In other functional languages, like Haskell (that is the first name of Haskell Curry), functions are always curried.

## 13 Comments

• Great examples, thanks for sharing

• A little bit perplexed by your Partial implementation... Instead of

public static Func<T2, Func<T3, TResult>> Partial<T1, T2, T3, TResult>(this Func<T1, T2, T3, TResult> function, T1 arg1) {...}

I'd rather write

public static Func<T2, T3, TResult>> Partial<T1, T2, T3, TResult>(this Func<T1, T2, T3, TResult> function, T1 arg1)
{
return (arg2, arg3) => function(arg1, arg2, arg3);
}

• It was a very good education. No site has this quality. Thank you

• Thanks a lot.

• Not sure the use of currying serves any purpose over the use of closures in C#. The only reason I've seen for currying is that it allows partial application, but in fact, in C# partial application is more flexible with the use of a closure, because you can choose *which* parameter to specify. Consider

Func<int, int, int> subtract = (a, b) => a - b;
Func<int, int> takeAway2 = a => subtract(a, 2);

var result = takeAway2(6); //result is 4

• Wonderful website. Plenty of helpful information here. I?¦m sending it to a few buddies ans also sharing in delicious. And certainly, thank you in your sweat! <a href="https://www.totosite365.info" target="_blank" title="토토사이트">토토사이트</a>

• This is such a great resource that you are providing and you give it away for free. I love seeing blog that understand the value of providing a quality resource for free. <a href="https://www.slotmachine777.site" target="_blank" title="슬롯머신사이트">슬롯머신사이트</a>

• https://ma-study.blogspot.com/

• Of course, your article is good enough, bitcoincasino but I thought it would be much better to see professional photos and videos together. There are articles and photos on these topics on my homepage, so please visit and share your opinions.

• I'm writing on this topic these days, <a href="https://google.com.pg/url?sa=t&url=https%3A%2F%2Fwww.mtclean.blog/">majorsite</a>, but I have stopped writing because there is no reference material. Then I accidentally found your article. I can refer to a variety of materials, so I think the work I was preparing will work! Thank you for your efforts.

• I've been looking for photos and articles on this topic over the past few days due to a school assignment, <a href="https://google.com.pe/url?sa=t&url=https%3A%2F%2Fwww.mtclean.blog/">bitcoincasino</a> and I'm really happy to find a post with the material I was looking for! I bookmark and will come often! Thanks :D

• I've been troubled for several days with this topic. <a href="https://google.com.pa/url?sa=t&url=https%3A%2F%2Fwww.mtclean.blog/">safetoto</a>, But by chance looking at your post solved my problem! I will leave my blog, so when would you like to visit it?

• The assignment submission period was over and I was nervous, <a href="https://google.com.om/url?sa=t&url=https%3A%2F%2Fwww.mtclean.blog/">casino online</a> and I am very happy to see your post just in time and it was a great help. Thank you ! Leave your blog address below. Please visit me anytime.

Add a Comment

As it will appear on the website

Not displayed

Your website