title

Q.E.D. Code

Michael L Perry

0
Followers
0
Plays
Q.E.D. Code

Q.E.D. Code

Michael L Perry

0
Followers
0
Plays
OVERVIEWEPISODESYOU MAY ALSO LIKE

Details

About Us

Explore the intersection between software and mathematics. Michael L Perry takes you on a journey through the history of computing, information theory, cryptography, distributed systems, and everywhere else that math has influenced technology. Not only will you dive into math papers, but you'll also learn valuable programming techniques that you can apply in any language.Code Erat Demonstrandum

Latest Episodes

QED 19: Dependency Tracking

The number of degrees of freedom in a system is equal to its number of unknowns minus its number of equations. That is also equal to the number of independent variables in the system. Dependent variables do not contribute degrees of freedom. However, by taking advantage of determinism, we can compute at run time the set of independent variables upon which a dependent variable depends. This gives libraries like Update Controls, Assisticant, and Knockout the ability to figure out when to update the viewwith extreme efficiency. Both C# and Java have enumerables. These are interfaces understood by the looping constructs of the language itself. Unfortunately, it is unsafe to modify a collection whileusing an iterator. But immutable data types hold the key, and should be the preferred way of managing collections. Prime numbers are the building blocks of all natural numbers. Godel used them to prove his Incompleteness Theorem. There are many mind-blowing facts that we know about prime numb...

17 MIN2016 OCT 24
Comments
QED 19: Dependency Tracking

Q.E.D. 18: Paxos

Leslie Lamport wrote a paper describing the Paxos algorithm in plain English. This is an algorithm that guarantees that a distributed system reaches consensus on the value of an attribute. Lamport claims that the algorithm can be derived from the problem statement, which would imply that it is the only algorithm that can achieve these results. Indeed, many of the distributed systems that we use today are based at least in part on Paxos. Linq not only introduced the ability to query a database directly from C#. It also introduced a set of language features that were useful in their own right. Lambda expressions did not exist in C# prior to 3.0, but now they are preferred to their predecessor, anonymous delegates. Extension methods were added to the language specifically to make Linq work, but nevertheless provide an entirely new form of expressiveness. Linq works because its parts were designed to compose. This is not quite so true of language features that came later, like async and...

16 MIN2016 SEP 19
Comments
Q.E.D. 18: Paxos

QED 17: Pythagoras

The Pythagoreans were a cult of Greek mathematicians that believed that all things were composed of large enough integers. Their leader, Pythagoras, is best known for the proof that the square of the hypotenuse of a right triangle is equal to the sum of the squares of the two sides. Unfortunately, this theorem leads to the conclusion that some numbers cannot be expressed as the ratio of large enough integers, and so proof destroyed their beliefs. Monads are an extremely useful category of type. Whereas Applicatives let us build pipelines of single values, Monads support forking within that pipeline. They provide a "bind" method that joins a function returning another Monad to the end of the pipeline, and then flattens out the result. We can use this to build queries, to eliminate null reference exceptions, and even to execute asynchronous code without nested callbacks. Event Sourcing, popularized by Greg Young, is the practice of storing the events that have occurred in a system, in...

16 MIN2016 AUG 28
Comments
QED 17: Pythagoras

QED 16: Elements

Euclid's Elements takes a disciplined, formal approach to proving assertions based only on simple axiomatic statements. While most of these axioms are elegant, one of them is more complex and wordy. It seems as if it should be provable from the others. Several mathematicians have tried, but eventually they found a surprising result. Beware when provingyour own assertions that you don't make the mistake of assuming something that seems obvious. Category theory isn't as complex as you might be lead to believe. A category is nothing more than a contract that sets rules on how a type is to behave. Functors, despite having a weird name, are just types that can map functions into a different space. The List type is an example of a functor, because it can transform a function on its elements into a function on lists. And Applicatives are just wrapper types. They are especially useful for building pipelines. CQRS, Command Query Responsibility Segregation, is a pattern thatapplies the Single...

17 MIN2016 AUG 15
Comments
QED 16: Elements

QED 15: The Y Combinator

The Lambda Calculus uses simple replacement to compute expressions. However, it does not define a way to replace a parameter of a function with the function itself. That would seem to make it impossible to write recursive functions. However, with a clever bit of self-application, we can define a function thatmakes any other function recursive. This is the Y-Combinator. Claude Shannon told us that it was important to keep equivocation high in order to make a cypher difficult to crack. In the second half of his paper, he tells us how to do that. We need to diffuse the message, and we need to confuse the key. Doing these two things will destroy the statistical patterns of the message so that the only possible attack is brute force. The Two Generals problem has no solution. But does that mean that we cannot guarantee that a distributed system will reach consensus? Not at all. By applying two simplifying assumptions, we reduce the problem to one that can be solved with a very simple prot...

19 MIN2016 JUL 17
Comments
QED 15: The Y Combinator

QED 14: Equivocation

Claude Shannon followed up one incredibly important paper with a second of even greater significance. In Communication Theory of Secrecy Systems, he analyzes cryptosystems based on the probabilities of certain plaintext messages given an intercepted cyphertext. Understanding this form of analysis will help us to design more effective systems. The Lambda Calculus computes using nothing but symbol replacement. If we are going torun programs like a computer, we need to express conditional branches. We can represent the value "true" as a functionλa.λb.a. In other words, the function that returns thefirst of two arguments. Similarly, thevalue "false" is represented by the functionλa.λb.b. To create a conditional "if-else" statement, capture two branches and then apply the third argument to select between them:λa.λb.λc.c a b. Suppose that you needed to reach an agreement among several people by passing messages. Now suppose that some of those people could not be trusted. Under what...

16 MIN2016 JUL 3
Comments
QED 14: Equivocation

QED 13: The First Program

in a translation of a paper on the Analytical Engine, Ada Lovelace improved upon L. F. Menambrea's work by applying rigor to the calculations that he performed. But then she took things one iteration further. In fact, she took thingsn iterations further. She wrote the first computer program, using the backtracking feature of the Analytical Engine to perform loops. The Lambda Calculus contains only functions. Evaluating a function is merely rewriting it to replace itsparameter with its argument. How then can we represent something like numbers in a language with no primitives? We do it by writing a function that calls another function a certain number of times. The function that calls it once is the number 1. The function that calls it 100 times is the number 100. Alonzo Church demonstrated that these "Church Numerals" could be operated upon by other functions to calculate any computable number. We gain a great deal of confidence in our code if we can reason about the value of variab...

19 MIN2016 JUN 18
Comments
QED 13: The First Program

QED 12: Difference Engine

The Difference Engine was a mechanical computer that could calculate tables of numbers based on polynomials. Theamazing thing is, though, that it could only add. How then could it accomplish this feat? By the method of differences! Charles Babbage never constructed his Difference Engine, but we've made a couple from his designs. Lambda Calculus is also a method of computation based on really simple rules. In this case, they are alpha-conversion, beta-conversion, and eta-conversion. These serious-sounding transforms are actually pretty simple. Let's first learn what they are, and then see how they relate to C#. Speaking of C#, Malachi asks a question about C# constructors. As you may know, I am of the opinion that constructor parameters should represent only immutable fields. How, then, does one initialize a mutable field in such a way that you can guarantee that it is set? In other words, write a method on the classthat can only be called after the object is initialized.

17 MIN2015 JUL 20
Comments
QED 12: Difference Engine

QED 11: The Lambda Calculus

Alonzo Church invented The Lambda Calculus as a simple set of rules that, when applied correctly, could compute anything that you could do with a pencil and paper. But all it is is simple replacement. Learn the basics of lambda expressions so that we can build on this theory of computation. As we celebrate pi day in the States (where we put the month in the wrong place -- 3/14/15), let's see how we go about computing the digits of pi. We'll start out with a simple geometric method, and progress through more modern techniques, until we arive at a truly surprising and remarkable formula. When John von Neumann created Game Theory, he showed how it can sometimes find an optamal strategy. But there's one game for which it fails completely. Find out why The Prisoner's Dilemma is such a tricky problem, and how a fair algorithm was found to be the best possible solution.

17 MIN2015 MAR 26
Comments
QED 11: The Lambda Calculus

QED 10: The Two Generals Problem

ListenerRichard Allen writes to ask about proving enough of a program correct to constrain the number of tests that must be written. I respond that you need both tests and proof.Otherwise, how could you know that the specification is what you intended? Two generals wish toreach consensus by sending messengers through enemy territory. How can this be achieved? You can prove, in fact, that it cannot. This has important rammifications on the design of distributed systems. To prove thatprerequisites are satisfied before calling a method, you can use a factory method. By chaining these factory methods together, you can prove that an entire sequence of events must take place in the correct order. This makes a fluend API not only more readable, but also more provable.

13 MIN2015 MAR 9
Comments
QED 10: The Two Generals Problem

Latest Episodes

QED 19: Dependency Tracking

The number of degrees of freedom in a system is equal to its number of unknowns minus its number of equations. That is also equal to the number of independent variables in the system. Dependent variables do not contribute degrees of freedom. However, by taking advantage of determinism, we can compute at run time the set of independent variables upon which a dependent variable depends. This gives libraries like Update Controls, Assisticant, and Knockout the ability to figure out when to update the viewwith extreme efficiency. Both C# and Java have enumerables. These are interfaces understood by the looping constructs of the language itself. Unfortunately, it is unsafe to modify a collection whileusing an iterator. But immutable data types hold the key, and should be the preferred way of managing collections. Prime numbers are the building blocks of all natural numbers. Godel used them to prove his Incompleteness Theorem. There are many mind-blowing facts that we know about prime numb...

17 MIN2016 OCT 24
Comments
QED 19: Dependency Tracking

Q.E.D. 18: Paxos

Leslie Lamport wrote a paper describing the Paxos algorithm in plain English. This is an algorithm that guarantees that a distributed system reaches consensus on the value of an attribute. Lamport claims that the algorithm can be derived from the problem statement, which would imply that it is the only algorithm that can achieve these results. Indeed, many of the distributed systems that we use today are based at least in part on Paxos. Linq not only introduced the ability to query a database directly from C#. It also introduced a set of language features that were useful in their own right. Lambda expressions did not exist in C# prior to 3.0, but now they are preferred to their predecessor, anonymous delegates. Extension methods were added to the language specifically to make Linq work, but nevertheless provide an entirely new form of expressiveness. Linq works because its parts were designed to compose. This is not quite so true of language features that came later, like async and...

16 MIN2016 SEP 19
Comments
Q.E.D. 18: Paxos

QED 17: Pythagoras

The Pythagoreans were a cult of Greek mathematicians that believed that all things were composed of large enough integers. Their leader, Pythagoras, is best known for the proof that the square of the hypotenuse of a right triangle is equal to the sum of the squares of the two sides. Unfortunately, this theorem leads to the conclusion that some numbers cannot be expressed as the ratio of large enough integers, and so proof destroyed their beliefs. Monads are an extremely useful category of type. Whereas Applicatives let us build pipelines of single values, Monads support forking within that pipeline. They provide a "bind" method that joins a function returning another Monad to the end of the pipeline, and then flattens out the result. We can use this to build queries, to eliminate null reference exceptions, and even to execute asynchronous code without nested callbacks. Event Sourcing, popularized by Greg Young, is the practice of storing the events that have occurred in a system, in...

16 MIN2016 AUG 28
Comments
QED 17: Pythagoras

QED 16: Elements

Euclid's Elements takes a disciplined, formal approach to proving assertions based only on simple axiomatic statements. While most of these axioms are elegant, one of them is more complex and wordy. It seems as if it should be provable from the others. Several mathematicians have tried, but eventually they found a surprising result. Beware when provingyour own assertions that you don't make the mistake of assuming something that seems obvious. Category theory isn't as complex as you might be lead to believe. A category is nothing more than a contract that sets rules on how a type is to behave. Functors, despite having a weird name, are just types that can map functions into a different space. The List type is an example of a functor, because it can transform a function on its elements into a function on lists. And Applicatives are just wrapper types. They are especially useful for building pipelines. CQRS, Command Query Responsibility Segregation, is a pattern thatapplies the Single...

17 MIN2016 AUG 15
Comments
QED 16: Elements

QED 15: The Y Combinator

The Lambda Calculus uses simple replacement to compute expressions. However, it does not define a way to replace a parameter of a function with the function itself. That would seem to make it impossible to write recursive functions. However, with a clever bit of self-application, we can define a function thatmakes any other function recursive. This is the Y-Combinator. Claude Shannon told us that it was important to keep equivocation high in order to make a cypher difficult to crack. In the second half of his paper, he tells us how to do that. We need to diffuse the message, and we need to confuse the key. Doing these two things will destroy the statistical patterns of the message so that the only possible attack is brute force. The Two Generals problem has no solution. But does that mean that we cannot guarantee that a distributed system will reach consensus? Not at all. By applying two simplifying assumptions, we reduce the problem to one that can be solved with a very simple prot...

19 MIN2016 JUL 17
Comments
QED 15: The Y Combinator

QED 14: Equivocation

Claude Shannon followed up one incredibly important paper with a second of even greater significance. In Communication Theory of Secrecy Systems, he analyzes cryptosystems based on the probabilities of certain plaintext messages given an intercepted cyphertext. Understanding this form of analysis will help us to design more effective systems. The Lambda Calculus computes using nothing but symbol replacement. If we are going torun programs like a computer, we need to express conditional branches. We can represent the value "true" as a functionλa.λb.a. In other words, the function that returns thefirst of two arguments. Similarly, thevalue "false" is represented by the functionλa.λb.b. To create a conditional "if-else" statement, capture two branches and then apply the third argument to select between them:λa.λb.λc.c a b. Suppose that you needed to reach an agreement among several people by passing messages. Now suppose that some of those people could not be trusted. Under what...

16 MIN2016 JUL 3
Comments
QED 14: Equivocation

QED 13: The First Program

in a translation of a paper on the Analytical Engine, Ada Lovelace improved upon L. F. Menambrea's work by applying rigor to the calculations that he performed. But then she took things one iteration further. In fact, she took thingsn iterations further. She wrote the first computer program, using the backtracking feature of the Analytical Engine to perform loops. The Lambda Calculus contains only functions. Evaluating a function is merely rewriting it to replace itsparameter with its argument. How then can we represent something like numbers in a language with no primitives? We do it by writing a function that calls another function a certain number of times. The function that calls it once is the number 1. The function that calls it 100 times is the number 100. Alonzo Church demonstrated that these "Church Numerals" could be operated upon by other functions to calculate any computable number. We gain a great deal of confidence in our code if we can reason about the value of variab...

19 MIN2016 JUN 18
Comments
QED 13: The First Program

QED 12: Difference Engine

The Difference Engine was a mechanical computer that could calculate tables of numbers based on polynomials. Theamazing thing is, though, that it could only add. How then could it accomplish this feat? By the method of differences! Charles Babbage never constructed his Difference Engine, but we've made a couple from his designs. Lambda Calculus is also a method of computation based on really simple rules. In this case, they are alpha-conversion, beta-conversion, and eta-conversion. These serious-sounding transforms are actually pretty simple. Let's first learn what they are, and then see how they relate to C#. Speaking of C#, Malachi asks a question about C# constructors. As you may know, I am of the opinion that constructor parameters should represent only immutable fields. How, then, does one initialize a mutable field in such a way that you can guarantee that it is set? In other words, write a method on the classthat can only be called after the object is initialized.

17 MIN2015 JUL 20
Comments
QED 12: Difference Engine

QED 11: The Lambda Calculus

Alonzo Church invented The Lambda Calculus as a simple set of rules that, when applied correctly, could compute anything that you could do with a pencil and paper. But all it is is simple replacement. Learn the basics of lambda expressions so that we can build on this theory of computation. As we celebrate pi day in the States (where we put the month in the wrong place -- 3/14/15), let's see how we go about computing the digits of pi. We'll start out with a simple geometric method, and progress through more modern techniques, until we arive at a truly surprising and remarkable formula. When John von Neumann created Game Theory, he showed how it can sometimes find an optamal strategy. But there's one game for which it fails completely. Find out why The Prisoner's Dilemma is such a tricky problem, and how a fair algorithm was found to be the best possible solution.

17 MIN2015 MAR 26
Comments
QED 11: The Lambda Calculus

QED 10: The Two Generals Problem

ListenerRichard Allen writes to ask about proving enough of a program correct to constrain the number of tests that must be written. I respond that you need both tests and proof.Otherwise, how could you know that the specification is what you intended? Two generals wish toreach consensus by sending messengers through enemy territory. How can this be achieved? You can prove, in fact, that it cannot. This has important rammifications on the design of distributed systems. To prove thatprerequisites are satisfied before calling a method, you can use a factory method. By chaining these factory methods together, you can prove that an entire sequence of events must take place in the correct order. This makes a fluend API not only more readable, but also more provable.

13 MIN2015 MAR 9
Comments
QED 10: The Two Generals Problem
hmly
himalayaプレミアムへようこそ聴き放題のオーディオブックをお楽しみください。