Protocol Oriented Programming

This is technically a post in the Lambda Calculus series but I am concerned with the implementation of my Lambda calculator today. Anybody who has looked at the code will see I have used a class hierarchy to represent Lambda expressions. I use classes because I want my objects to be of reference types so that I can build a recursive tree easily and without infinitely large structs. I use a hierarchy because, although there are three types of Lambda expression (variable, abstraction and application), they are often interchangeable: an application has two components, a function and an argument, both of which may be any type of Lambda expression.

Classes and class hierarchies are not considered to be very Swifty. We are all supposed to do protocol oriented programming these days. Personally, I would think that is nonsense: use the paradigm the problem demands. However, this does lead to some problems and ugliness in the Lambda Calculator code. Swift classes do not support abstract methods formally. You cannot write a superclass with certain methods unimplemented but that must be implemented by subclasses. In Java, you can write

class Foo
{
    abstract int bar();
}

The function bar() is unimplemented in Foo but must be implemented in any subclass that can be instantiated. If it’s not, an error is flagged when the compiler reaches the instantiation statement. This does not exist in Swift. Instead, in my code, you’ll see methods defined like this:

class Expression: Encodable
{
    ...
    func count(freeVariable: FreeVariable) -> Int
    {
        mustBeOverridden(self)
    }
    ...
}

mustBeOverridden(self) is a call to a function defined in Toolbox that calls fatalError() with a diagnostic that tells you which function in which class caused the error. This is a poor man’s abstraction because you don’t find out until run time that your subclass doesn’t define a function it should. This sort of thing ought to be detectable by the compiler.

Abstract functions have been requested several times on the Swift Evolution message board but the answer is always the same: “you should be using protocols” or similar. So, I’m going to see if I can come up with a protocol oriented design for the Lambda Calculator. I’m hoping that it will lead to a cleaner design with more flexibility for extension (e.g. for a typed lambda calculus). I’ll also figure out a way to do some performance testing, although performance isn’t really a concern for the Lambda calculator: it’s a teaching aid.

Source Code Organisation

I had several thoughts about how to organise the new code e.g. whether to do it in parallel, to replace or even create a new repository. In the end, it’s just a new branch that will, for the moment, replace the existing code. Follow progress on the branch protocol-oriented-programming.

Stage 1: Nuke Everything

I had a class hierarchy that looked like this:

I think the leaves will remain concrete classes. Expression will be a protocol and possibly, Variable too. We may decompose Expression into multiple behaviours, e.g. there may be a protocol for alpha reduction and for beta reduction.

Anyway, the first stage is to comment everything out and turn Expression into a protocol. Then to fix the compiler errors. After that, I will fix the unit tests and finally get the REPL working again.

It’ll probably take a while to fix everything again, but the nuked code is tagged pop-1.