Summary

  • Inheritance can be used to override methods.
  • This could be used to memoize a recursive function for example.
  • Dynamic dispatch can be desugared to continuation passing: a functional concept.
  • This style of continuation passing can be denoted as “Open Recursion” because the recursive calls are left open to be overridden.

Memoization Using Inheritance

class Base {
a() {
console.log('Base Method A');
}
}
class Derived extends Base {
b() {
console.log('Derived Method B');
super.a();
}
}
const derived = new Derived();
derived.b();

It’s also possible to do the opposite and call…


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

If this sentence is true, then Santa Claus is real.

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…


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


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

If you think this article is too long, you can skip to Should I refactor my code? below

Introduction

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?


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.


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.


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.

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 {…


Summary:

Using “open” recursion:

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

Memoization in Rust.

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);
}

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

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