Archives
-
Category Theory via C# (23) Performance
In functional programming, there are many powerful tools and patterns, like lambda expression, purity, deferred execution, immutability, fluent LINQ query composition, … But everything has a cost. As Alan Perlis said:
-
Category Theory via C# (22) More Monad: Continuation Monad
In C#, callback is frequently used. For example, a very simple Add function, without asynchrony:
-
Category Theory via C# (21) More Monad: Writer< , > Monad
Unlike the Reader< , > monad, the Writer< , > monad output contents with a sequence of functions:
-
Category Theory via C# (20) More Monad: Reader< , > Monad
Sometimes there are functions work with a shared environment. Typical examples are:
-
Category Theory via C# (19) More Monad: State< , > Monad
State machine (or finite state machine) represents a abstract machine with one state or a number of state. C# use state machine a lot. For example:
-
Category Theory via C# (18) More Monad: IO<> Monad
As mentioned in a previous part, in purely functional programming, functions cannot have side effects. For example, when defining LINQ queries, laziness and purity are expected. So, how should the impure actions be managed in purely functional programming or LINQ? For example:
-
Category Theory via C# (17) Monad-like Tuple<>, Task<>, IQueryable<> And IQbservable<>
Theoretically, Tuple<> should be counted as the Id<> monad. However, it is lack of laziness. In the context of C# and LINQ, it is only monad-like.
-
Category Theory via C# (16) More Monads: Lazy<>, Func<>, Nullable<>, ParallelQuery<> And IObservale<>
Again, Lazy<> is the simplest monad, it is just the lazy version of Tuple<>, and should be considered as the Id<> monad. This is the implementation of its SelectMany:
-
Category Theory via C# (15) IEnumerable<> Monad And LINQ: SelectMany For All
Previous part introduced SelectMany for monad IEnumerable<>. Actually SelectMany is more than meets the eye, and can be used to implement other LINQ queries.
-
Category Theory via C# (14) Monad And IEnumerable<>
A previous part showed endofunctor category is a monoid (the entire category itself). An endofunctor In the endofunctor category can be monoid too. This kind of endofunctor is called monad. Formally, monad is an endofunctor of category C, equipped with 2 natural transformations:
-
Category Theory via C# (13) Monoidal Functor-like Tuple<> And Task<>
Theoretically, Tuple<> should be counted as the Id<> monoidal functor. However, as previously mentioned, it is lack of laziness.
-
Category Theory via C# (12) More Monoidal Functors: Lazy<>, Func<> And Nullable<>
Lazy<> should be the simplest monoid functor - it is just the lazy version of Tuple<>. And in these posts it will be considered as the Id<> monoidal functor.
-
Category Theory via C# (11) Monoidal Functor And IEnumerable<>
Given monoidal categories (C, ⊗, IC) and (D, ⊛, ID), a monoidal functor (or lax monoidal functors) is a functor F: C → D equipped with:
-
Category Theory via C# (10) Monoidal Category
A previous part demonstrated endofunctor category is monoidal. Now with the help of bifunctor, the general abstract monoidal category can be defined. A monoidal category is a category C equipped with:
-
Category Theory via C# (9) Bifunctor
As discussed in all the previous functor parts, a functor is a wrapper of a object with a “Select” ability to preserve a morphism to another‘
-
Category Theory via C# (8) Functor Category
Given 2 categories C and D, functors C → D forms a functor category, denoted DC:
-
Category Theory via C# (7) Natural Transformation
If F: C -> D and G: C -> D are both functors from categories C to category D, a mapping can be constructed between F and G, called natural transformation and denoted η : F ⇒ G.
-
Category Theory via C# (6) Functor-like Tuple<>, Task<> And IQueryable<>
Tuple<> looks like the simplest functor by just wrapping a value. It is most close to the Identity functor of Haskell. Its Select functions are:
-
Category Theory via C# (5) More Functors: Lazy<>, Func<> And Nullable<>
A simple functor in DotNet category is Lazy<>. Its Select functions can be easily implemented:
-
Category Theory via C# (4) Functor And IEnumerable<>
A functor F: C → D is a structure-preserving mapping from category C to category D:
-
Category Theory via C# (3) Monoid as Category
An individual monoid (T, ⊙, I) can be a category M:
-
Category Theory via C# (2) Monoid
A monoid, denoted a 3-tuple (M, ⊙, I), is a set M with
-
Category Theory via C# (1) Fundamentals - Category, Object And Morphism
This post and the following posts will introduce category theory and its important concepts via C# and LINQ, including functor, applicative functor, monoid, monad, etc. Categories were first introduced by Samuel Eilenberg and Saunders Mac Lane in 1942–45. It might be tedious, as Wikipedia pointed:
-
Lambda Calculus via C# (23) Y Combinator, And Divide
p is the fixed point of function F if and only if:
-
Lambda Calculus via C# (22) Iota Combinator and Jot Combinators
Iota is an esoteric programming language with minimum elements but still Turing-complete. Iota's universal combinator is:
-
Lambda Calculus via C# (21) SKI Combinator Calculus
The previous part shows SKI calculus is untyped and strongly typed C# implementation does not work. So here comes the SKI in untyped C#:
-
Lambda Calculus via C# (20) Combinators
As mentioned in a fundamental part, combinator is a special kind of lambda expression without free variables. So combinatory logic (introduced by Moses Schönfinkel and Haskell Curry) can be viewed as a variant of lambda calculus.
-
Lambda Calculus via C# (19) Church Encoding, And More
So far a ton has been encoded. Here is a summary.
-
Lambda Calculus via C# (18) Encoding Signed Number
In lambda calculus, a signed number (integer) can be represented by a Church pair (2-tuple) of Church numerals (natural numbers):
-
Lambda Calculus via C# (17) Encoding Church List with Fold (Aggregate) Function
A third way to encode Church list, is to use fold function (also called aggregate in C#/.NET):
-
Lambda Calculus via C# (16) Encoding Church List with 2 Church Pairs as a Node
Previous part encoded Church list with one Church pair (2-tuple) as a list node. An alternative way is to use 2 tuples as a node, one wrapping the other.
-
Lambda Calculus via C# (15) Encoding Church List with Church Pair, And Null
This part will demonstrate how to use lambda expressions to encode another data structure - list (Church list in lambda calculus or LinkedList<T> in .NET).
-
Lambda Calculus via C# (14) Church Pair (2-Tuple) and Church Numeral Decrease
In the Church numeral arithmetic part, the Decrease was defined as:
-
Lambda Calculus via C# (13) Encoding Church Pairs (2-Tuples) and Generic Church Booleans
Church pair is the Church encoding of the pair type, aka 2-tuple. Unlike the Tuple<T1, T2> class in .NET, in lambda calculus Church pair will be represented by lambda expression. To avoid 2 naming systems, here in all the code, Church pair will be called tuple.
-
Lambda Calculus via C# (12) Church Numeral Comparison Operators
With the predicates defined in previous part, operators can be defined in _Numeral class. Once again, class does not exist in lambda calculus, but C# class provides a place to define operators, which greatly improve the readability.
-
Lambda Calculus via C# (11) Predicates, And Divide
A predicate is a function that returns a Boolean value. In Church encoding of lambda calculus, a predicate is a lambda expression that returns a Church Boolean.
-
Lambda Calculus via C# (10) Church Numeral Arithmetic Operators
Another benefits of introducing (cheating with) _Numeral class into lambda calculus is - it provides a place to define custom operators.
-
Lambda Calculus via C# (9) Wrapping Church Numerals And Arithmetic
In previous part, the Decrease function was a Func<Numeral<Func<Func<T, T>, T>>, Numeral<T>>:
-
Lambda Calculus via C# (8) Church Numeral Arithmetic
The previous part defined Church numerals in lambda calculus and implemented 0, 1, 2, 3 in 2 different ways. By observing the definition and code, there are some patterns when the Church numeral increases from 0 to 3.
-
Lambda Calculus via C# (7) Encoding Church Numerals
Previous parts showed that Boolean values, Boolean logic, and if logic can all be encoded by lambda expressions. This and next few articles will focus on natural numbers. Signed number will be encoded after introducing Church pairs (2-tuples).
-
Lambda Calculus via C# (6) If Logic, And Reduction Strategies
The if logic is already built in Church Booleans.
-
Lambda Calculus via C# (5) Boolean Logic
After defining Boolean values True and False with functions, now the Boolean logics can be encoded, by functions too.
-
Lambda Calculus via C# (4) Encoding Church Booleans
After clarifying the concepts and terms, a lot of implementation coding starts from this part.
-
Lambda Calculus via C# (3) Fundamentals - Function composition
It may not be the best place to discuss function composition in the lambda calculus series. However, function composition will be used a lot in later articles, so here is a brief introduction.
-
Lambda Calculus via C# (2) Fundamentals - Lambda Expression, Variables, Reductions
The C# lambda expression has been discussed in detail. This post will explain lambda expression and other concepts in lambda calculus.
-
Lambda Calculus via C# (1) Fundamentals - Closure, Currying and Partial Application
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.
-
Entity Framework Core and LINQ to Entities (9) Performance
The previous parts has discussed some aspects that can impact the performance of EF/Core and LINQ to Entities, and here is a summary:
-
Parallel LINQ in Depth (4) Performance
Parallel LINQ is powerful, but also can be more complex. This part discusses Parallel LINQ query performance in different cases.
-
Parallel LINQ in Depth (3) Query Methods (Operators)
Parallel LINQ provides additional query methods and additional overrides for Aggregate method:
-
Parallel LINQ in Depth (2) Partitioning
The first step of Parallel LINQ is partitioning. The source values is split into several partitions, so that multiple threads can execute the query logic in parallel.
-
Parallel LINQ in Depth (1) Local Parallel Query and Visualization
So far, all the discussion for LINQ to Objects/XML does not involve multi-threading, concurrency, or parallel computing. This is by design, because pulling values from an IEnumerable<T> sequence is not thread-safe.When multiple threads simultaneously access one IEnumerable<T> sequence, race condition can occur and lead to unpredictable consequence. As a result, all the LINQ to Objects/XML queries are implemented in a sequential manner with a single thread. To scale LINQ in multi-processor environment, Since .NET Framework4.0, a parallel version of LINQ to Objects is also provided, called Parallel LINQ or PLINQ.
-
LINQ to XML in Depth (3) Manipulating XML
Besides creating and querying XML, LINQ to XML also provides APIs for other XML manipulations, including cloning, deleting, replacing, and updating XML structures:
-
LINQ to XML in Depth (2) Query Methods (Operators)
As fore mentioned, LINQ to XML is just a specialized LINQ to Objects, so all the LINQ to Objects query methods can be used in LINQ to XML queries. LINQ to XML provides many function members and other methods for XML tree navigation, ordering, XPath querying, etc. The following list shows these functions and their return types:
-
LINQ to XML in Depth (1) Modeling XML
XML (eXtensible Markup Language) is widely used to represent, store, and transfer data. Since .NET 3.5, the built in LINQ to XML APIs are provided to enable LINQ queries for XML data source. These APIs are located in System.Xml.XDocument NuGet package for .NET Core, and System.Xml.Linq.dll for .NET Framework. LINQ to XML can be viewed as specialized LINQ to Objects, where the objects in memory represents XML structures.
-
LINQ to Objects in Depth (7) Custom Query Methods
After discussing the query methods provided by .NET, this part demonstrates how to define custom query methods:
-
LINQ to Objects in Depth (6) Interactive Extensions (Ix)
Besides the built-in query methods (standard query operators) provided by System.Linq.Enumerable, Microsoft also provides additional query methods through the System.Interactive NuGet package (aka Interactive Extensions (Ix) library), which has a System.Linq.EnumerableEx type with the following query methods:
-
LINQ to Objects in Depth (5) Query Methods Implementation
Understanding of internals of query methods is very helpful for using them accurately and effectively, and is also helpful for defining custom query methods, which is discussed later in this chapter. Just like the usage discussion part, here query methods are still categorized by returned type, but in a different order:
-
LINQ to Objects in Depth (4) Deferred Execution, Lazy Evaluation and Eager Evaluation
As fore mentioned, when a generator method (method contains yield statement and returns IEnumerable<T>) is compiled to a pure function, which constructs a generator and return it to caller. So at runtime, when a generator method is called, the values in output sequence is not pulled or evaluated. This is called deferred execution.
-
LINQ to Objects in Depth (3) Generator
After understanding how to use LINQ to Objects, starting from this part, the implementation of query methods is discussed. Most LINQ to Object query methods are implemented with iteration pattern and generators.
-
LINQ to Objects in Depth (2) Query Methods (Operators) and Query Expressions
This part discusses the usages of built-in LINQ to Objects query methods and query expressions. As fore mentioned, these query methods (also called standard query operators) are provided in System.Linq.Enumerable type, most of which are IEnumerable<T> extension methods. They can be categorized by return type:
-
LINQ to Objects in Depth (1) Local Sequential Query
LINQ to Objects queries sequences of .NET objects in local memory of current .NET application or service. Its data source and the queries are represented by IEnumerable<T>.
-
C# Functional Programming In-Depth (15) Pattern matching
Pattern matching is a common feature in functional languages. C# 7.0 introduces basic pattern matching, including constant value as pattern and type as pattern, and C# 7.1 supports generics in pattern matching.
-
C# Functional Programming In-Depth (14) Asynchronous Function
Asynchronous function can improve the responsiveness and scalability of the application and service. C# 5.0 introduces async and await keywords to greatly simplify the async programming model.
-
C# Functional Programming In-Depth (13) Pure Function
Functional programming encourages modeling operations with pure functions.
-
C# Functional Programming In-Depth (12) Immutability, Anonymous Type, and Tuple
Immutability is an important aspect of functional paradigm. As fore mentioned, imperative/object-oriented programming is usually stateful, and functional programming encourages immutability without state change. In C# programming, there are many kinds of immutability, but they can be categorized into 2 levels: immutability of some value, and immutability of some value’s internal state. Take local variable as example, a local variable can be called immutable, if once it is assigned, there is no way to reassign to it; a local variable can also be called immutable, if once its internal state is initialized, there is no way to modify its state to different state.
-
C# Functional Programming In-Depth (11) Covariance and Contravariance
In covariance and contravariance, variance means the capability to substitute a type with a more derived type or less derived type in a context. The following is a simple inheritance hierarchy:
-
C# Functional Programming In-Depth (10) Query Expression
C# 3.0 introduces query expression, a SQL-like query syntactic sugar for query methods composition.
-
C# Functional Programming In-Depth (9) Function Composition and Chaining
In object-oriented programming, objects can be composed to build more complex object. Similarly, in functional programming. functions can be composed to build more complex function.
-
C# Functional Programming In-Depth (8) Higher-order Function, Currying and First Class Function
Higher-order function is a function accepting one or more function parameters as input, or returning a function as output. The other functions are called first-order functions. C# supports higher-order function from the beginning. Generally, C# function can have almost any data type and function type as its input types and output type, except:
-
C# Functional Programming In-Depth (7) Expression Tree: Function as Data
C# lambda expression is a powerful syntactic sugar. Besides representing anonymous function, the same syntax can also represent expression tree.
-
C# Functional Programming In-Depth (6) Anonymous Function and Lambda Expression
Besides named function represented by method members, C# also supports anonymous functions, represented by anonymous method or lambda expression with no name at design time. This part discussed lambda expression as a functional feature of C# language. In the meanwhile, the general concept of lambda expression is the core of lambda calculus, where functional programming originates. General lambda expression and lambda calculus will be discussed in the Lambda Calculus chapter.
-
C# functional programming in-depth (5) Delegate: Function type, instance and group
In C#, functions are represented by methods of types, and other function members of types. In C#, just like just objects have types, methods/functions have types too, which are represented by delegate type.
-
C# functional programming in-depth (4) Function input and output
In C#, by default, arguments are passed to parameters by value. In the following example, the PassByValue function has a Uri parameter and a int type parameter. Uri is class so it is reference type, and int is structure so it is value type:
-
C# functional programming in-depth (3) Local Function and Closure
C# 7.0 introduces local function, which allows defining and calling a named, inline function inside a function member’s body. Unlike a local variable, which has to be used after being defined, a local function can be called before or after it is defined:
-
C# functional programming in-depth (2) Named function and function polymorphism
In C#, the most intuitive functions are method members of class and structure, including static method, instance method, and extension method, etc. These methods have names at design and are called by name, so they are named functions. Some other method-like members, including static constructor, constructor, finalizer, conversion operator, operator overload, property, indexer, event accessor, are also named functions, with specific name generated by at compiled time. This chapter discusses named functions in C#, how these named functions are defined, and looks into how they work. Method member’s name is available at design time, which some other function members’ name are generated at compile time.
-
C# functional programming in-depth (1) C# language fundamentals
C# 1.0 was initially released in 2002, as its first language specification says at the beginning, C# is a “simple, modern, object oriented, and type-safe” programming language for general purpose. Now C# has evolved to 7.2. During the years, a lot of great language features, especially rich functional programming features, has been added to C#. Now C# language has been productive and elegant, imperative and declarative, object-oriented and functional. With frameworks like .NET Framework, .NET Core, Mono, Xamarin, Unity, etc., C# is used by millions of people cross different platforms, including Windows, Linux, Mac, iOS, Android, etc.
-
Functional Programming and LINQ Paradigm (3) Programming Paradigms and Functional Programming
Programming paradigm is the fundamental style of programming. There are many paradigms for programming, for example:
-
Functional Programming and LINQ Paradigm (2) LINQ Overview
As fore mentioned, LINQ consists of syntax in languages and APIs in libraries:
-
Functional Programming and LINQ Paradigm (1) Getting Started with .NET/Core, C# and LINQ
This is a tutorial of functional programming and LINQ in C# language. The contents was initially based on my LINQ via C# talks. Hope it helps.
-
Remote desktop connection authentication error due to CredSSP encryption oracle remediation
Recently, when connecting to another Windows machine with RD, I got the following RDP authentication error due to CredSSP encryption oracle remediation:
-
End-to-end: Setup PHP Debugging for Visual Studio Code on Windows
This is a quick tutorial of minimum installation and configurations of development environment for PHP programming, including Apache, PHP, and Visual Studio Code (VSCode) on 64 bit Windows.
-
Port Microsoft Concurrency Visualizer SDK to .NET Standard and NuGet
I uploaded a NuGet package of Microsoft Concurrency Visualizer SDK: ConcurrencyVisualizer. Microsoft Concurrency Visualizer is an extension tool for Visual Studio. It is a great tool for performance profiling and multithreading execution visualization. It also has
a SDK library to be invoked by code and draw markers and spans in the timeline. I used it to visualize sequential LINQ and Parallel LINQ (PLINQ) execution in my Functional Programming and LINQ tutorials. For example, array.Where(…).Select(…) sequential LINQ query and array.AsParallel().Where(…).Select(…) Parallel LINQ query can be visualized as following spans: