Gain insights into tackling uncertainty in C# programming. Delve into improving System.Random class with powerful techniques for efficient problem-solving and fewer bugs. Discover new language uses.

csharp.tar.gz

ep10

ep11

ep12

ep13

ep14

ep15

ep16

ep17

bonus01

ep18

ep20

ep21

ep22

ep24

ep23

ep25

ep26

ep27

ep28

ep29

ep30

ep31

ep32

ep33

ep34

ep36

ep37

ep38

There are a lot of problems we face in programming that deal with uncertainty, statistics, and probabilities. Unfortunately, the majority of the general-purpose languages that we use on a daily basis don’t provide a great approach to solving them.

This is particularly the case in C# with the System.Random class. The implementations of this class have been pretty poor for some time. System.Random in C# regularly leads to unexpected, buggy outcomes.

If you’re a C# fan who’s looking for new ways to use the language, then this course is for you. It proposes different approaches to improving the System.Random class, providing a number of powerful techniques that solve problems more efficiently and with fewer lines of code.

Fixing Random: Techniques in C#

## Stripped Down C#
Without further ado, here is our proposed stripped-down C# that could be a domain-specific language (DSL) for `probabilistic` workflows; as we’ll see, it is quite similar to both enumerator blocks from C# 2, and `async`/`await` from C# 5.

### Workflow
* The workflow must be a function with a `return` type of `IDiscreteDistribution<T>` for some `T`.

* Just as methods that use `await` must be marked `async`, our DSL methods must be marked `probabilistic`.

* The function has an ordinary function body: a block of statements.

We are using C# 5 asynchronous workflows as an example of how to add a new mechanism to C#. The statements and the expressions in a `probabilistic` method are restricted as follows:

1. Declaration statements must have an initializer.

2. All the locals must have unique names throughout the method.

3. Assignments can only be in declarations or as statements; no use of assignments in the middle of an expression is allowed.

4. No compound assignments, increments or decrements.

5. No `await`, `yield`, `try`, `throw`, `switch`, `while`, `do`, `break`, `continue`, `goto`, `fixed`, `lock`, `using` or labeled statements allowed. What’s left? `if` and `return` statements are fine, as well as blocks `{ }`. We told you we are stripping things down!

6. No `lambdas`, anonymous functions, or query comprehensions.

7. No use of `in`, `out` or `ref`.

7. All the other perfectly normal operations are allowed — function calls, object initializers, member access, indexers, arithmetic, that’s all just fine.

8. However, all function calls and whatnot must be pure; there can be no side effects, and nothing should throw.

Basically what we are doing here is making a little super-simple subset of C# that doesn’t have any of the weird, hard stuff that keeps compiler writers busy. In this pleasant world, locals are always assigned, there are no closures, there are no worries about what happens when an exception is thrown and all that sort of stuff.

We’ll sketch out how to soften some of those restrictions in later lessons. We want to show that we can describe how to implement a simple core of a language; harder features can come later.

## New Unary Operator and Statement
To this little language, we are going to add a new unary operator and a new statement. The new operator is `sample`, and it may appear only as of the right operand of an assignment, or the initializer of a declaration:

```C#
int x = sample WeightedInteger.Distribution(8, 2, 7, 3);
```

The operand must be of type `IDiscreteDistribution<T>`, and the type of the expression is `T`. Again, this should feel familiar if you’re used to `await`.

The new statement is a condition, and it has the form
```C#
condition expression;
```

The expression must be convertible to `bool`. The meaning of this thing is much the same as `Where`: if the Boolean condition is not met, then a value is filtered out from the distribution by setting its weight to zero.

> Aside: In the [previous lesson](https://www.educative.io/courses/fixing-random-techniques-in-c-sharp/musings-about-language-design) we learned a bit about how language designers must choose how general or specific a language element is, and that this must be reflected in syntax; this is an excellent example of such a choice.

We have chosen `condition` because we can think of this operation as creating a conditional distribution; we could have said `where` instead of `condition` and had it mean basically the same thing, but that would be moving towards the established C# jargon for sequences, which we are explicitly trying to avoid.

However, as we’ve seen, a primary usage case for a conditional distribution is computing the posterior distribution when given a prior and a likelihood. But why do we wish to compute the posterior at all? Typically because we have observed something. That is, the development cycle of the `probabilistic` program is:

* Before the program is written, data scientists and developers compute priors, like "What percentage of emails are spam?"
* They also compute likelihood functions: "what word combinations are likely, given that an email is spam? What word combinations are likely given that an email is not spam?"
* A spam detection program must now answer the question: given that we have observed an email with certain word combinations, what is the posterior probability that it is spam? This is where the `probabilistic` workflow comes in.
For that reason, we could reasonably choose `observation` or `observe` as our keyword here, instead of `condition`, emphasizing to the developer "the reason you use this feature is to express the computation of a posterior distribution for a given observation." That would make the feature feel a little bit less general but might help more clearly express the desired semantics in the mind of the typical programmer designing a workflow that computes a posterior.

We are going to stick with `condition`, but let's point out that this is a choice that has user experience consequences, were we actually to implement this feature in a language like C#.

Let’s look at some examples:

```C#
probabilistic IDiscreteDistribution<bool> Flip()
{
  int x = sample Bernoulli.Distribution(1, 1);
  return x == 0;
}
```

What we would like is for this method to have the same semantics as if we had written:

```C#
 IDiscreteDistribution<bool> Flip() => 
   Bernoulli.Distribution(1, 1).Select(x => x == 0);
```

What do you think about these two implementations? The former looks a lot more like the straightforward, imperative code that we’re used to.

Let’s look at another:

```C#
probabilistic IDiscreteDistribution<int> TwoDSix()
{
  var d = SDU.Distribution(1, 6);
  int x = sample d;
  int y = sample d;
  return x + y;
}
```

Again, it seems that this is more clear than

```C#
IDiscreteDistribution<int> TwoDSix() 
{
  var d = SDU.Distribution(1, 6);
  return from x in d from y in d select x + y;
}
```

And it certainly seems more evident, particularly to the novice, than

``` C#
IDiscreteDistribution<int> TwoDSix() 
{
  var d = SDU.Distribution(1, 6);
  return d.SelectMany(x => d, (x, y) => x + y);
}
```

LINQ is incredible for sequences, but the statement-based workflow is much easier to understand for distributions.

Now let’s look at a complicated workflow, this one with conditioning:

```C#
probabilistic IDiscreteDistribution<string> Workflow(int z)
{
  int ii = sample TwoDSix();
  if (ii == 2)
    return "two";
  condition ii != z;
  bool b = sample Flip();
  return b ? "heads" : ii.ToString();
}
```

The first two were easy to see how they corresponded to query syntax, but what even is the distribution represented by this workflow? It depends on the value of the parameter `z`, for one thing.

What we want here is: when you call this method, you get a distribution back. When you `Sample()` that distribution, it should logically have the same effect as all the sample operations `Sample()` their operand, and the returned value is, well, the returned value. However, if any condition is false, then we abandon the current attempt and start over.

The trick is implementing those semantics without actually running the body in a loop!

> **Exercise:** Pick a value for `z`; let’s say 3. See if you can work out what the distribution of strings is that should come out the other end of this thing. We will provide the answer to this exercise in the next lesson.

> **Exercise:** If you had to represent this workflow as a query, how would you do it?

## Implementation
The code snippet below is non-executable because this is our very own proposed implementation. We will make it executable in the next lesson.

# Stripped Down C#
Without further ado, here is our proposed stripped-down C# that could be a domain-specific language (DSL) for `probabilistic` workflows; as we’ll see, it is quite similar to both enumerator blocks from C# 2, and `async`/`await` from C# 5.

## Workflow
* The workflow must be a function with a `return` type of `IDiscreteDistribution<T>` for some `T`.

* Just as methods that use `await` must be marked `async`, our DSL methods must be marked `probabilistic`.

* The function has an ordinary function body: a block of statements.

We are using C# 5 asynchronous workflows as an example of how to add a new mechanism to C#. The statements and the expressions in a `probabilistic` method are restricted as follows:

1. Declaration statements must have an initializer.

2. All the locals must have unique names throughout the method.

3. Assignments can only be in declarations or as statements; no use of assignments in the middle of an expression is allowed.

4. No compound assignments, increments or decrements.

5. No `await`, `yield`, `try`, `throw`, `switch`, `while`, `do`, `break`, `continue`, `goto`, `fixed`, `lock`, `using` or labeled statements allowed. What’s left? `if` and `return` statements are fine, as well as blocks `{ }`. We told you we are stripping things down!

6. No `lambdas`, anonymous functions, or query comprehensions.

7. No use of `in`, `out` or `ref`.

7. All the other perfectly normal operations are allowed — function calls, object initializers, member access, indexers, arithmetic, that’s all just fine.

8. However, all function calls and whatnot must be pure; there can be no side effects, and nothing should throw.

Basically what we are doing here is making a little super-simple subset of C# that doesn’t have any of the weird, hard stuff that keeps compiler writers busy. In this pleasant world, locals are always assigned, there are no closures, there are no worries about what happens when an exception is thrown and all that sort of stuff.

We’ll sketch out how to soften some of those restrictions in later lessons. We want to show that we can describe how to implement a simple core of a language; harder features can come later.

# New Unary Operator and Statement
To this little language, we are going to add a new unary operator and a new statement. The new operator is `sample`, and it may appear only as of the right operand of an assignment, or the initializer of a declaration:

```C#
int x = sample WeightedInteger.Distribution(8, 2, 7, 3);
```

The operand must be of type `IDiscreteDistribution<T>`, and the type of the expression is `T`. Again, this should feel familiar if you’re used to `await`.

The new statement is a condition, and it has the form
```C#
condition expression;
```

The expression must be convertible to `bool`. The meaning of this thing is much the same as `Where`: if the Boolean condition is not met, then a value is filtered out from the distribution by setting its weight to zero.

> Aside: In the [previous lesson](https://www.educative.io/courses/fixing-random-techniques-in-c-sharp/musings-about-language-design) we learned a bit about how language designers must choose how general or specific a language element is, and that this must be reflected in syntax; this is an excellent example of such a choice.

We have chosen `condition` because we can think of this operation as creating a conditional distribution; we could have said `where` instead of `condition` and had it mean basically the same thing, but that would be moving towards the established C# jargon for sequences, which we are explicitly trying to avoid.

However, as we’ve seen, a primary usage case for a conditional distribution is computing the posterior distribution when given a prior and a likelihood. But why do we wish to compute the posterior at all? Typically because we have observed something. That is, the development cycle of the `probabilistic` program is:

* Before the program is written, data scientists and developers compute priors, like "What percentage of emails are spam?"
* They also compute likelihood functions: "what word combinations are likely, given that an email is spam? What word combinations are likely given that an email is not spam?"
* A spam detection program must now answer the question: given that we have observed an email with certain word combinations, what is the posterior probability that it is spam? This is where the `probabilistic` workflow comes in.
For that reason, we could reasonably choose `observation` or `observe` as our keyword here, instead of `condition`, emphasizing to the developer "the reason you use this feature is to express the computation of a posterior distribution for a given observation." That would make the feature feel a little bit less general but might help more clearly express the desired semantics in the mind of the typical programmer designing a workflow that computes a posterior.

We are going to stick with `condition`, but let's point out that this is a choice that has user experience consequences, were we actually to implement this feature in a language like C#.

Let’s look at some examples:

```C#
probabilistic IDiscreteDistribution<bool> Flip()
{
  int x = sample Bernoulli.Distribution(1, 1);
  return x == 0;
}
```

What we would like is for this method to have the same semantics as if we had written:

```C#
 IDiscreteDistribution<bool> Flip() => 
   Bernoulli.Distribution(1, 1).Select(x => x == 0);
```

What do you think about these two implementations? The former looks a lot more like the straightforward, imperative code that we’re used to.

Let’s look at another:

```C#
probabilistic IDiscreteDistribution<int> TwoDSix()
{
  var d = SDU.Distribution(1, 6);
  int x = sample d;
  int y = sample d;
  return x + y;
}
```

Again, it seems that this is more clear than

```C#
IDiscreteDistribution<int> TwoDSix() 
{
  var d = SDU.Distribution(1, 6);
  return from x in d from y in d select x + y;
}
```

And it certainly seems more evident, particularly to the novice, than

``` C#
IDiscreteDistribution<int> TwoDSix() 
{
  var d = SDU.Distribution(1, 6);
  return d.SelectMany(x => d, (x, y) => x + y);
}
```

LINQ is incredible for sequences, but the statement-based workflow is much easier to understand for distributions.

Now let’s look at a complicated workflow, this one with conditioning:

```C#
probabilistic IDiscreteDistribution<string> Workflow(int z)
{
  int ii = sample TwoDSix();
  if (ii == 2)
    return "two";
  condition ii != z;
  bool b = sample Flip();
  return b ? "heads" : ii.ToString();
}
```

The first two were easy to see how they corresponded to query syntax, but what even is the distribution represented by this workflow? It depends on the value of the parameter `z`, for one thing.

What we want here is: when you call this method, you get a distribution back. When you `Sample()` that distribution, it should logically have the same effect as all the sample operations `Sample()` their operand, and the returned value is, well, the returned value. However, if any condition is false, then we abandon the current attempt and start over.

The trick is implementing those semantics without actually running the body in a loop!

> **Exercise:** Pick a value for `z`; let’s say 3. See if you can work out what the distribution of strings is that should come out the other end of this thing. We will provide the answer to this exercise in the next lesson.

> **Exercise:** If you had to represent this workflow as a query, how would you do it?

# Implementation
The code snippet below is non-executable because this is our very own proposed implementation. We will make it executable in the next lesson.

In this lesson we are going to propose a stripped-down version of C# and introduce a new operator.

Proposed Stripped-Down C#

Introduction to System.Random in C#

Introduction to Fixing Random

Fixing Random - Discrete Distribution

Fixing Random - Continuous Distribution

Conclusion

Appendix

Proposed Stripped-Down C#

Stripped Down C#

Workflow