Image for post
Image for post

Summary

  • Curry’s paradox allows proofs of any statement in some languages that have the ability to construct a self referential sentence.
  • This paradox allows a proof of any statement, no matter how absurd.
  • Some statically typed programming languages allow for basic logical statements to be made and subsequently proven. Typescript is one of these languages.

The Premise

This statement seems innocuous enough, but it exposes a fatal flaw in some logical systems. If it is possible for the above sentence to exist as a statement, then it follows that Santa Claus is real…


Image for post
Image for post
It’s a switch. Use it.

Summary

  • Switch statements over basic enums have lots of disadvantages.
  • Many of the limitations can be overcome by using either dynamic dispatch, or the visitor pattern depending on your use case.
  • In languages that support sum types natively, consider using those instead of the visitor pattern.

Introduction

I have seen several articles recently that take the position that switch statements (or even if statements) are an anti-pattern in regards to best practice object-orientated programming. In a way, the sentiment is usually fine, but I don’t think that these articles really tell the full story. …


Summary

  • “Don’t repeat yourself” (DRY) is a widely accepted programming principle, but it has several limitations
  • An alternative derivation of DRY is presented, that aims to alleviate some of these limitations
  • Programs are made up of functions, and to make functions maximally reusable they should:
    - Have the most lenient preconditions
    - Have the most strict postconditions
    - Perform the smallest amount of non-trivial work

Introduction

Image for post
Image for post
An example of an abstraction

In software engineering, “clean code” is a sought after ideal. Code that is “clean” is easy to read…


Recently I made a game and entered it into the Github Game Off 2019. The premise of the game is that there are a series of cows that run around following rules. The aim in the earlier levels is to get all of the cows into a green area. The aim in later levels is to use the cows to create and program a basic computer.

With these kinds of game jams, there is a restrictive time limit involved. In this case, 30 days. On day 0, you receive a theme in which to base your game upon: the theme…


Summary:

  • A persistent data structure can easily keep track of previous versions of itself with little overhead.
  • A regular data structure can be converted into a persistent one by replacing instances of Box with Rc, and replacing mutable dereferences with Rc::make_mut.
  • The resulting structure is both more performant and uses less memory if you plan on performing lots of clones.

What is a persistent data structure?

Data structures are persistent when they can keep track of all of their old states. Every time a modification is made, a new structure is created instead of modifying the original data. …


Summary

  • Child entities which are both mutable and shared can make any, or all of their parents invalid.
  • In freeform shared mutability, we cannot cache any calculation that depends on a shared mutable entity.
  • If we limit the scope of sharing to code we trust not to invalidate our cache, then we can cache results as much as we like.
  • Limiting the scope of sharing implies that we have some kind of container entity: an Arena.

Interfaces, encapsulation and references.

First of all a disclaimer. I’m going to use the terms such as “interface” and “encapsulation”, and I’m going to define them a little bit…


Summary

  • For the majority of code, shared mutability is usually not required.
  • We cannot have sharing, mutability and “internal consistency”. A program that tries to have all three is provably incorrect.
  • If we want sharing, and mutability but do not need “internal consistency”, we can use a file, a database handle, a mutex, or any other similar structure.
  • If we need mutability, and “internal consistency” but do not need sharing, we can have all modifications go through a common ancestor.
  • If we need sharing, and “internal consistency” but not mutability, we can freeze our data, or have persistent data structures.

The problem with shared mutability.

Safe…


Summary

  • Closures are a combination of a function pointer (fn) and a context.
  • A closure with no context is just a function pointer.
  • A closure which has an immutable context belongs to Fn.
  • A closure which has a mutable context belongs to FnMut.
  • A closure that owns its context belongs to FnOnce.

Understanding the different types of closures in Rust.

Image for post
Image for post

Unlike some other languages, Rust is explicit about our use of the self parameter. We have to specify self to be the first parameter of a function signature when we are implementing a struct:

struct MyStruct {
text: &'static str,
number: u32,
}
impl MyStruct { fn new (text…


Summary:

Using “open” recursion:

  • We can memoize functions without modifying the syntax of the function.
  • We can make functions generic across multiple types of memoization.

Memoization in Rust.

Consider a recursive function. The most basic example is the Fibonacci sequence. Here is a naive implementation:

fn fib_naive(arg: u32) -> u32 {
match arg {
0 => 0,
1 => 1,
n => fib_naive(n - 1) + fib_naive(n - 2),
}
}
fn main() {
assert_eq!(fib_naive(40), 102334155);
}
Image for post
Image for post

Calculating fib_naive(40) on my computer takes almost a second. If we look at this function, we can reason…


What is an invariant?

  • Aim to write programs so that you cannot create invalid objects or data.
Image for post
Image for post

I’ll use Rust as the language to describe the concepts behind this post, but try to make it accessible to those using other languages.

We can start with a simple object, such as a circle. A circle is completely defined by it’s radius. As long as our radius is positive, we have a valid circle:

#[derive(Debug)]
struct Circle {
radius: f64
}
impl Circle {
fn new_option (radius: f64) -> Option<Circle> {
if radius > 0.0 …

Andrew Pritchard

The stories I write are a part of a learning journey through life, logic and programming. Share this journey with me.

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store