Structure and Interpretation of Computer Programmers

I make it easier and faster for you to write high-quality software.

Friday, November 16, 2018

A little challenge

A little challenge today: create a JS function that turns its arguments into a list of pairs. Actually, the brief was “using Ramda” but I ended up not doing that:

function basePairwise(xs) {
  if (xs.length == 0) return [];
  if (xs.length == 1) return [[xs[0], undefined]];
  return [[xs[0], xs[1]]].concat(basePairwise(xs.slice(2)));

function pairwise(...xs) {
  return basePairwise(xs);

One of the nice things about JavaScript (I won’t say that often, so note the date) is the introspective nature: the fact that I get to just look at the way a function was called, rather than saying “you must use exactly these types and this arity always”. Here, I’ve done that with the JS spread operator: I could have used the arguments pseudo-list for only a little more work.

posted by Graham at 17:52  

Saturday, July 22, 2017

If Object-Oriented Programming were announced today

Here’s an idea: the current backlash against OOP is actually because people aren’t doing OOP, they’re doing whatever they were doing before OOP. But they’re calling it OOP, because the people who were promoting OOP wanted them to believe that they were already doing OOP.

Why is that? Because the people who were promoting OOP wanted to sell their things. They were doing this in the 1980s to 1990s, when you could still expect developers to spend thousands of dollars on tools and libraries. “Here’s a thing that’s completely unlike what you’re already doing” is not as good a sales pitch as “ride the latest wave without boiling the ocean”. Object-Oriented principles were then hidden by the “Object Technology” companies – the StepStones, NeXTs, OTIs, OMGs – who wanted to make OOP accessible in order to sell their Object Technology.

That’s not the world of 2017. Nowadays, developer environments, libraries, deployment platforms etc are largely open source and free or very cheap, so rather than make an idea seem accessible, people try to make it seem important. We see that with the current wave (third wave? I’m not sure) of functional programming evangelism, where people are definitely trying to show that they are “functionaller than thou” rather than that you already know this stuff. Throw up a github or an npm that uses monad, pointfree or homoiconic without any indication of shame, and you’re functionalling right. Demonstrating that it’s already possible to curry methods in Objective-C is not the right way to functional.

If OOP were introduced into this world, you’d probably have a more dogmatic, “purer” representation of it than OOP as popularly practised today. You might even have OOP in Java.

One thing that makes me think that is that, well, it’s happened and it’s true. Multiple times. As previously explored here, protocol-oriented programming is just polymorphism under another name, and polymorphism will be found in a big-letters heading in any OOP book (in Barbara Liskov’s “Program Development in Java”, it’s chapter 8, “Polymorphic Abstractions”. In Bertrand Meyer’s “Touch of Class”, section 16.2, “Polymorphism”.

Similarly, what are microservices other than independent programs that maintain their own data and the operations on those data, performing those operations in response to receiving messages? What is a router at the front of a microservice but the message dispatch handler, picking a method implementation by examining the content of a selector?

posted by Graham at 15:24  

Thursday, July 28, 2016

Dogmatic paradigmatism

First, you put all of your faith in structured programming, and you got burned. You found it hard to associate the operations in your software with the data upon which they act, and to make sure that the expectations made on the data in one place are satisfied when that data has been modified in that other place, or over there in yet another place. Clearly structured programming is broken.

Then, you put all of your faith in object-oriented programming, and you got burned. You found it hard to follow the flow of a program when it jumps in and out of different classes, and to see which parts were coupled to what. Clearly object-oriented programming is broken.

Then, you put all of your faith in functional programming, and you got burned. You found it hard to represent real business processes in terms of immutable data structures and pure functions, and to express changes to the operating environment without using side effects. Clearly functional programming is broken.

Or maybe it’s you. Maybe, rather than relying on faith to make these conceptual thought frameworks do what you need from them, you could have thought about the concepts.

posted by Graham at 08:50  

Sunday, October 11, 2015

*-Oriented Programming

Much is written about various paradigms or orientations of programming: Object- (nee Message-) Oriented, Functional, Structured, Dataflow, Logic, and probably others. These are often presented as camps or tribes with which to identify. A Smalltalk programmer will tell you that they are an Object-Oriented programmer, and furthermore those Johnny-come-latelies with their Java are certainly not members of the same group. A Haskell programmer will tell you that they are a functional programmer, and that that is the only way to make working software (though look closely; their Haskell is running on top of a large body of successful, imperative C code).

Notice the identification of paradigms with individual programming languages. Can you really not be object-oriented if you use F#, or is structured programming off-limits to an Objective-C coder? Why is the way that I think so tightly coupled to the tool that I choose to express my thought?

Of course, tools are important, and they do have a bearing on the way we think. But that’s at a fairly low, mechanical level, and programming is supposed to be about abstraction and high-level problem solving. You’re familiar with artists working with particular tools: there are watercolour painters and there are oil painters (and there are others too). Now imagine if the watercolour painting community (there is, of course, no such thing) decreed that it’s impossible to represent a landscape using oil paints and the oil painting community declared that watercolours are “the wrong tools for the job” of painting portraits.

This makes no sense. Oil paints and watercolour paints define how the paint interacts with the canvas, the brush, and the paint that’s already been applied. They don’t affect how the painter sees their subject, or thinks about the shapes involved and the interaction of light, shadow, reflection, and colour. They affect the presentation of those thoughts, but that’s at a mechanical low level.

Programming languages define how the code interacts with the hardware, the libraries, and the code that’s already been applied. They don’t affect how the programmer sees their problem, or thinks about the factors involved. They affect the presentation of those thoughts, but that’s at a mechanical low level.

Function-oriented Objects

Given a Cartesian representation of the point (x,y), find its distance from the origin and angle from the x axis.

I’m going to approach this problem using the principles of functional programming. There’s clearly a function that can take us from the coordinates to the displacement, and one that can take us from the coordinates to the angle. Ignoring the implementation for the moment, they look like this:

Point_radius :: float, float -> float
Point_angle  :: float, float -> float

This solution has its problems. I have two interchangeable arguments (both the x and y ordinates are floats) used in independent signatures, how do I make it clear that these are the same thing? How do I ensure that they’re used in the same way?

One tool in the arsenal of the functional programmer is pattern matching. I could create a single entry point with an enumeration that selects the needed operation. Now it’s clear that the operations are related, and there’s a single way to interpret the arguments, guaranteeing consistency.

Point :: float, float, Selector -> float

Good for now, but how extensible is this? What if I need to add an operation that returns a different type (for example a description that returns a string), or one that needs other arguments (for example the projection on to a different vector)? To provide that generality, I’ll use a different tool from the functional toolbox: the higher-order function. Rewrite Point so that instead of returning a float, it returns a function that captures the coordinates and takes any required additional arguments to return a value of the correct type. To avoid cluttering this example with irrelevant details, I’ll give that function a shorthand named type: Method.

Point :: float, float, Selector -> Method

You may want to perform multiple operations on values that represent the same point. Using a final functional programming weapon, partial application, we can capture the coordinates and let you request different operations on the same encapsulated data.

Point :: float, float -> Selector -> Method

Now it’s clear to see that the Point function is a constructor of some type that encapsulates the coordinates representing a given two-dimensional Cartesian point. That type is a function that, upon being given a Selector representing some operation, returns a Method capable of implementing that operation. The function implements message sending, and Points are just objects!

Imagine that we wanted to represent points in a different way, maybe with polar coordinates. We could provide a different function, Point', which captures those:

Point' :: float, float -> Selector -> Method

This function has the same signature as our original function, it too encapsulates the constructor’s arguments (call them instance variables) and returns methods in response to selectors. In other words, Point and Point' are polymorphic: if they have methods for the distance and angle selectors, they can be used interchangeably.

Object-oriented Functions

Write a compiler that takes source code in some language and creates an executable. If it encounters malformed source code, it should report an error and not produce an executable.

Thinking about this with my object-oriented head, I might have a Compiler object with some method #compile(source:String) that returns an optional Executable. If it doesn’t work, then use the #getErrors():List<Error> method to find out what went wrong.

That approach will work (as with most software problems there are infinite ways to skin the same cat), but it’s got some weird design features. What will the getErrors() method do if it’s called before the compile() method? If compile() is called multiple times, do earlier errors get kept or discarded? There’s some odd and unclear temporal coupling here.

To clean that up, use the object-oriented design principle “Tell, don’t ask”. Rather than requesting a list of errors from the compiler, have it tell an error-reporting object about the problems as they occur. How will it know what error reporter to use? That can be passed in, in accordance with another OO principle: dependency inversion.

Compiler#compile(source:String, reporter:ErrorConsumer): Optional<Executable>
ErrorConsumer#reportError(error:Error): void

Now it’s clear that the reporter will receive errors related to the invocation of #compile() that it was passed to, and there’s no need for a separate accessor for the errors. This clears up confusion as to what the stored state represents, as there isn’t anyway.

Another object-oriented tool is the Single Responsibility Principle, which invites us to design objects that have exactly one reason to change. A compiler does not have exactly one reason to change: you might need to target different hardware, change the language syntax, adopt a different executable format. Separating these concerns will yield more cohesive objects.

Tokeniser#tokenise(source:String, reporter:ErrorConsumer): Optional<TokenisedSource>
Compiler#compile(source:TokenisedSource, reporter:ErrorConsumer): Optional<AssemblyProgram>
Assembler#assemble(program:AssemblyProgram, reporter:ErrorConsumer): Optional<BinaryObject>
Linker#link(objects:Array<BinaryObject>, reporter:ErrorConsumer): Optional<Executable>
ErrorConsumer#reportError(error:Error): void

Every class in this system is named Verber, and has a single method, #verb. None of them has any (evident) internal state, they each map their arguments onto return values (with the exception of ErrorConsumer, which is an I/O sink). They’re just stateless functions. Another function is needed to plug them together:

Binder<T,U,V>#bind(T->Optional<U>, U->Optional<V>): (T->Optional<V>)

And now we’ve got a compiler constructed out of functions constructed out of objects.

Brain-oriented programming

Those examples were very abstract, not making any use of specific programming languages. Because software design is not coupled to programming languages, and paradigmatic approaches to programming are constrained ways to think about software design. They’re abstract enough to be separable from the nuts and bolts of the implementation language you choose (whether you’ve already chosen it or not).

Those functions in the Point example could be built using the blocks available in Smalltalk, Ruby or other supposedly object-oriented languages, in which case you’d have objects built out of functions that are themselves built out of objects (which are, of course, built out of functions…). The objects and classes in the Compiler example can easily be closures in a supposedly functional programming language. In fact, closures and blocks are not really too dissimilar.

What conclusions can be derived from all of this? Clearly different programming paradigms are far from exclusive, so the first lesson is that you don’t have to let your choice of programming language dictate your choice of problem solving approach (nor do you really have to do it the other way around). Additionally where the approaches try to solve the same problem, the specific techniques they comprise are complementary or even identical. Both functional and object-oriented programming are about organisation, decomposition and comprehensibility, and using either or even both can help to further those aims.

Ultimately your choice of tools isn’t going to affect your ability to think by much. Whether they help you express your thoughts is a different matter, but while expression is an important part of our work it’s only a small part.

Further Reading

The ideas here were primarily motivated by Uday Reddy’s Objects as Closures: Abstract Semantics of Object-Oriented Languages (weird embedded PDF reader link). In the real-life version of this presentation I also talked a bit about Theorems for Free (actual PDF link) by Philip Wadler, which isn’t so related but is nonetheless very interesting :).

posted by Graham at 13:53  

Tuesday, July 7, 2015

Imperative Programming in Swift

A cliche in programming is that certain ways of writing programs make it possible to “reason about” code. So it should be possible to form an argument that proceeds from some axioms to a conclusion about the code we’re looking at via some logical (or otherwise defensible) steps.

Looking at the declaration of this function, f:

func f<T>(xs:[T]) -> T

Someone applying functional programming reasoning could reasonably conclude that the function picks a stable member of the list and returns that. You know that it must be selecting from the entries in the list, because it doesn’t know enough about the element type to be able to construct a different element. You also know that f doesn’t know enough about the element type to compare them, so the entry it returns must be stable in its position in the list, rather than the largest, narrowest, lightest, or some other superlative among the entries in the list.

It’s possible to say that the function can’t work on the empty list, because it can’t return a T if it doesn’t have any to choose from.

So, was our hypothetical functional programmer correct? Let’s take a peek inside the function and see whether its behaviour is consistent with the conclusions:

func f<T>(xs:[T]) -> T {
  var error:NSError?
  let i = str.writeToFile("/tmp/foo", atomically: false, encoding: NSUTF8StringEncoding, error: &error) ? 0:1
  let j = NSFileManager.defaultManager().removeItemAtPath("/mach_kernel", error: &error) ? 1:2
  var k = 0
  errno = 37
  if let error = error {
    k += error.code
  let l = Int(drand48()*3)
  return xs[i+j+k-l]

They were correct in every respect! Except the one about the right answer, that didn’t go so well. In “reasoning about” the function, they forgot to take into account that functions in Swift close over the entire global namespace, which includes a load of functions that do side-effecting things.

Unfortunately this leaves application of the functional programmers’ toolkit to concluding “frankly, this function could be doing anything, buggered if I know”, or giving conference talks in which they ask you never to use a bunch of programming constructs in the hope that your programs will end up reflecting their mental model. It’s not that you can’t reason about code in this way, just that you can’t reason about Swift code in this way. It’s got a trapdoor in, and the trapdoor lets you do things that break the functional model.

That doesn’t mean throwing out reason completely, though. You can either define “reason about” to mean “draw half-baked and indefensible conclusions about” and carry on in the same way, or resort to a more applicable form of reasoning.

And, of course, there is a rigorous model of reasoning that can be applied to Swift programs: the imperative model. Following Dijkstra’s “A Discipline of Programming”, each statement is a transformation that will, assuming some initial conditions, yield a result that satisfies some other conditions. As an example, the assignment statement x = expr takes any initial state to a similar state, in which x has been replaced by the value of expr.

A program is a sequence of those transformations. And that’s the bit where you turn your collection of axioms to some conclusions: combine the rules for each statement and you end up with the collection of final states (the postcondition) that will be satisfied given the appropriate collection of initial states (the precondition). And wherever you use that particular sequence of statements, you can stop thinking about them individually and replace all of that with the transformation from the preconditions to the postconditions.

It turns out it’s not how you think about your program that makes it work. It’s doing the thinking. Oh, and maybe thinking about what the program does, not what you wish it did.

posted by Graham at 22:31  

Tuesday, June 23, 2015

Protocol-Oriented Programming in Objective-C

Hi, this is a guest post from Crusty. I’ve been doing a tour of the blogosphere, discussing Protocol-Oriented Programming. This time, Graham was kind enough to hand over the keyboard for SICPers and let me write a post here.

Back when Graham was talking about Object-Oriented Programming in Functional Programming in Swift, he mentioned that the number of methods you need to define on an object (or “procedural data type”) is actually surprisingly low. A set, Graham argued, is a single method that reports whether an object is a member of the set or not. An array has two methods: the count of objects it contains and the object at a particular index. We’re only talking about immutable objects here, but mutability can be modelled in immutable objects anyway.

Looking at the header or documentation for your favourite collections library, you probably think at this point that we’re missing something. Quite a few things, in fact. Your array data type probably has a few more than two methods, so how can those be the only ones you need?

Everything you might want to do to an array can be done in terms of those two methods that return the count and the object at an index. Any other operation can be built on those two operations (well, those two operations and a way to create some new objects). What’s more, any other array operation can be built using those operations without knowing how they’re implemented. That means we’re free to define them in a completely abstract way, using a protocol:

@protocol AnArray <NSObject>

- (NSUInteger)count;
- (id)objectAtIndex:(NSUInteger)index;


Now, without telling you anything about how that object works, I can create another object that “decorates” this array by using its methods. It can only call methods that are in the protocol, i.e. count and objectAtIndex:, but that’s sufficient. Hey, we’re doing protocol-oriented programming! As I said, we also need a way to create a new array sometimes, so for arguments’ sake let’s say that there’s a concrete version of AnArray called MyArray that the decorator knows how to create.

@interface ArrayDecorator : NSObject <AnArray>

- (instancetype)initWithArray:(id <AnArray>)anArray;

- (id)firstObject;
- (id <AnArray>)map:(SEL)aSelector;


@implementation ArrayDecorator
    id <AnArray> _array;

- (instancetype)initWithArray:(id <AnArray>)anArray
    self = [super init];
    if (!self) return nil;
    _array = anArray;
    return self;

- (NSUInteger)count { return [_array count]; }
- (id)objectAtIndex:(NSUInteger)index { return [_array objectAtIndex:index]; }

- (id)firstObject
    return [self count] ? [self objectAtIndex:0] : nil;

- (id <AnArray>)map:(SEL)aSelector
    void **buffer = malloc([self count] * sizeof(id));
    for (int i = 0; i < [self count]; i++) {
        buffer[i] = (__bridge void *)[[self objectAtIndex:i] performSelector:aSelector];
    id <AnArray> result = [[ArrayDecorator alloc] initWithArray:
        [[MyArray alloc] initWithObjects:(id *)buffer count:[self count]]];
    return result;


We’ve managed to create useful additional methods like firstObject and map:, that are only implemented in terms of the underlying array’s count and objectAtIndex:. It doesn’t matter how those methods are implemented, as long as they are.

Now, I know what you’re thinking. This protocol-oriented programming is fine and all, but now I have to remember to decorate every array I might create in order to get all of these useful additional methods. Wouldn’t it be great if there were some way to give all implementors of the AnArray protocol default implementations of map: and firstObject?

There is indeed a way to do that. This is what OOP’s inheritance feature is for. It’s been kindof abused, in that it’s overloaded to mean subtyping, which gets people into horrible knots over whether squares are rectangles or rectangles are squares (the answer, by the way, is yes). All inheritance really means is “if you send me a message I don’t have a method for, I’ll check to see if my parent class has that method”. In that case, this array decoration can be rewritten like this:

@interface SomeArray : NSObject 

- (NSUInteger)count;
- (id)objectAtIndex:(NSUInteger)index;
- (id)firstObject;
- (SomeArray *)map:(SEL)aSelector;


@implementation SomeArray

- (NSUInteger)count { [self doesNotRecognizeSelector:_cmd]; return 0; }
- (id)objectAtIndex:(NSUInteger)index { [self doesNotRecognizeSelector:_cmd]; return nil; }

- (id)firstObject
    return [self count] ? [self objectAtIndex:0] : nil;

- (SomeArray *)map:(SEL)aSelector
    void **buffer = malloc([self count] * sizeof(id));
    for (int i = 0; i < [self count]; i++) {
        buffer[i] = (__bridge void *)[[self objectAtIndex:i] performSelector:aSelector];
    SomeArray *result = [[MyArray alloc] initWithObjects:(id *)buffer count:[self count]];
    return result;


What’s changed? The methods that were previously defined on the AnArray protocol have been subsumed into the interface for SomeArray (which is what the word “protocol” used to mean in Smalltalk programming: the list of messages you could rely on an object responding to). Array implementations that are subclasses of SomeArray need merely implement count and objectAtIndex: (as before) and they automatically get all of the other methods, which are all implemented in terms of those two.

This looks familiar. Let me check the documentation for NSArray (this is from the Foundation 1.0 documentation on NeXTSTEP 3, by the way. They don’t call me Crusty for nothing.):

The NSArray class declares the programmatic interface to an object that manages an immutable array of objects. NSArray’s two primitive methods–count and objectAtIndex:–provide the basis for all the other methods in its interface. The count method returns the number of elements in the array. objectAtIndex: gives you access to the array elements by index, with index values starting at 0.

Interesting: all of its methods are implemented in terms of two “primitive” methods, called count and objectAtIndex:. The documentation also mentions that NSArray is a “class cluster”, and has this to say on class clusters:

Your subclass must override inherited primitives, but having done so can be sure that all derived methods that it inherits will operate properly.

Yes, that’s correct, protocol-oriented programming is a Crusty concept. We cornered it in the haunted fairground, removed its mask, and discovered that it was just abstract methods in object-oriented programming all along.

posted by Crusty Crustofferson at 22:55  

Sunday, June 14, 2015

Functional Programming in Object-Oriented Programming in Functional Programming in Swift

The objects that I’ve been building up over the last few posts have arbitrarily broad behaviours. They can respond to any selector drawn from the set of all possible strings.

As with all art, beauty is produced by imposing constraints. An important class (pardon the pun) of objects only has a meaningful response to one selector (value or, if it takes an additional argument, value:) which causes the object to do the one thing it knows how and return a result.

In many object-oriented programming circles, including the Smalltalk world, these objects are called blocks. They’re useful because they enable multiple uses of the same algorithm to be extracted into a single place, with the block customising the significant activity that happens in the algorithm. As an example, iterating an array to square numbers and iterating an array to load images from paths both involve iterating an array. The algorithm that iterates an array can be expressed in a form that accepts a block that does the work: squaring some numbers or loading some images.

Without going in to the details of the implementation (which is a collection of classes in the Objective-Swift system), here’s how a block could be used:

let myArray = newObject(NSArray(Integer(1, proto: o), Integer(2, proto: o),
  Integer(3, proto: o), Integer(4, proto: o)))
let evens = (myArray,"filter:") ✍ OneArgBlock({ obj in
  return (ℹ︎(obj)! % 2) == 0 ? True : False
  }, proto: o)
ℹ︎(evens→"count") // 2
📓((evens,"objectAtIndex:") ✍ Integer(0, proto: o)) // "2"
📓((evens,"objectAtIndex:") ✍ Integer(1, proto: o)) // "4"

The NSArray→filter: selector takes a block, and for each element in the array it sends the value: message with the element as the argument. In fact, it passes another block to the result of this block. Both True and False respond to the ifTrue: message. True→ifTrue: executes its argument, False→ifTrue: doesn’t.

Now we already have a name for the concept of an object that does exactly one thing, returning some result based on its input parameters. That’s a function. Yes, we finally got there:


So just as Object-Oriented Programming was a restricted application of a subset of Functional Programming, we can see Functional Programming as a restricted application of a subset of Object-Oriented Programming.

And that’s pretty much the point of this series of posts. These two ways of thinking about computer programs get you to the same place, as long as you apply the thinking. Neither is a silver bullet, neither is subsumed nor obsoleted by the other.


Now imagine a block that takes a selector and returns another block…

posted by Graham at 14:51  

Sunday, June 14, 2015

Classes in objects in object-oriented programming in functional programming in Swift

So far, Objective-Swift objects have used prototypical inheritance, in which they supply some methods but also know about another object to which they can forward messages they don’t understand themselves. This pattern is used in languages like Self, JavaScript and Io but is not common to other languages that also call themselves object-oriented programming languages.

Most OO languages have the idea of a “class” that supplies the methods for each object. An object knows that it “is a” specific realisation of its class, so when it receives a message it can look up the corresponding method in that class’s method table.

Like this.

typealias Class = Dictionary

// define a "Non-Standalone" Object that relies on a class for its methods.

let NSObject : Class = [ "description": IMP.description({ _ in return "An NSObject" })]

func newObject(isa : Class) -> Object {
  return { aSelector in
    if let anImplementation = isa[aSelector] {
      return anImplementation
    } else {
      return IMP.methodMissing({ _ in
        print("Does not recognize selector \(aSelector)")
        return nil

let anObject = newObject(NSObject)
📓(anObject) // "An NSObject"

Objects returned by the newObject() function look up their methods in their class dictionary, a table of method implementations for the corresponding selectors.

Not like that.

Mapping things to other things, that’s a function, isn’t it? And indeed there already is a type of function that takes selectors to methods, the object. A class should just be an object. Let’s try that again.

typealias Class = Object

let NSObject : Class = { aSelector in
  switch aSelector {
  case "description":
    return IMP.description({ _ in return "An NSObject" })
    return IMP.methodMissing({ _ in
      print("Instance does not recognize selector \(aSelector)")
      return nil

func newObject(isa : Class) -> Object {
  return { aSelector in
    return isa(aSelector)

let anObject = newObject(NSObject)
📓(anObject) // "An NSObject"

Great. Classes are objects, just as we’re used to. And indeed, a class could get its own methods from another class: a metaclass.

Notice that class-based objects walk and quack like the earlier, prototypical objects, so interoperate completely. That’s the point of message passing. No object needs to know how any other object works, just that it will respond to messages.

That’s what makes all of the bridges that let other languages interoperate with Objective-C. As long as objc_msgSend() can find your code and run it, we’re all good. In Objective-Swift, as long as passing you a selector gives me an IMP, we’re all good.

Instance variables.

Methods defined by classes should be able to see the object’s instance variables. The instance variables should, per their definition, be unique to each instance. However the best place to define them is in the class, for three reasons:

  1. The class knows which instance variables its methods expect to be present.
  2. The class’s constructor function captured the values (or the initial values, if they’re mutable) of the instance variables.
  3. If I’m subclassing, I want to be able to add the subclass’s instance variables to the superclass’s, without having to redefine the whole shebang.

So a class should tell its objects what instance variables it needs, and the values. Now, how should an instance look up its instance variables? We need to go from the name of an instance variable to its value, and I’ll save us both some embarrassment by cutting straight to the conclusion that an object is a great way to do this.

Each object in the class-based system will therefore be composed of two others: the class encapsulates what the object is and the methods it responds to, while the instance variable store encapsulates what the object is made of and what variables it has. Both are accessed through selectors, in a design choice that follows Eiffel and its Uniform-Access Principle (and the later Self language).

The same selector cannot refer both to a method and an ivar, because they’re both in the same namespace. One of them has to win, and in this case I’ve chosen the instance variable lookup to win.

Here’s a non-standalone version of Point, with its two instance variables. In the code shown here, o is a previously-defined object on which all methods are missing.

func NSPoint(x:Int, y:Int) -> Class {
  let superclass = NSObject
  let ivars:Object = { variableName in
    switch variableName {
    case "x":
      return .method({_ in return Integer(x, proto: o)})
    case "y":
      return .method({_ in return Integer(y, proto: o)})
      return (superclass→"instanceVariables")!(variableName)
  let thisClass:Class = { aSelector in
    switch aSelector {
    case "instanceVariables":
      return .method({_ in return ivars})
    case "distanceFromOrigin":
      return .method({(this, _cmd, args:Object...) in
        let thisX = ℹ︎(this→"x")!
        let thisY = ℹ︎(this→"y")!
        let distance = sqrt(Double(thisX*thisX + thisY*thisY))
        return Integer(Int(distance), proto: o)
      return superclass(aSelector)
  return thisClass

let aPoint = newObject(NSPoint(3,y: 4))
📓(aPoint) // "An NSObject"
📓(aPoint→"x") // "3"
📓(aPoint→"distanceFromOrigin") // "5"

Super calls.

You can see that NSPoint is a subclass of NSObject, although this isn’t amazingly useful. NSPoint gets all zero of NSObject‘s instance variables, and the not-particularly-descriptive description method.

In what might be the worst design choice of this blog, I’ll say that a 3D point is a specialisation of a 2D point. I’ll need to override distanceFromOrigin to calculate the distance in three dimensions, but I can use the result from the superclass’s two-dimensional calculation to do this.

As with Objective-C, this will require a different method lookup system, one that says “ask your superclass” instead of “ask yourself”. To do this, the object must know what its superclass is: it can ask its class. Here is a new method on NS3DPoint:

    case "superclass":
      return .method({ _ in return superclass })

Now, because I’m really running out of ideas on how to name these operators, here are some doubly-long operators that call into the superclass for an object:

infix operator .... {}

func .... (receiver: Object?, _cmd:Selector) -> IMP? {
  guard let this = receiver else { return nil }
  let method = (this→"superclass")!(_cmd)
  switch(method) {
  case IMP.methodMissing(let f):
    return f(this, _cmd)...._cmd
    return method

infix operator →→ {}

func →→ (receiver: Object?, _cmd:Selector) -> Object? {
  guard let imp = receiver...._cmd else { return nil }
  switch imp {
  case .method(let f):
    return f(receiver!, _cmd)
    return nil

Now, with all of this notation in place, it’s possible to create a method NS3DPoint→distanceFromOrigin that both overrides its parent method, and uses that overridden method in its calculation. Here’s the method:

    case "distanceFromOrigin":
      return .method({(this, _cmd, args:Object...) in
        let twoDDistance = ℹ︎(this→→"distanceFromOrigin")!
        let thisZ = ℹ︎(this→"z")!
        let distance = sqrt(Double(twoDDistance*twoDDistance + thisZ*thisZ))
        return Integer(Int(distance), proto: o)

Here it is in use:

let anotherPoint = newObject(NS3DPoint(10, y: 12, z: 14))
📓(anotherPoint→"distanceFromOrigin") // "20"


In many “classical” object-oriented programming systems, classes are just objects, which instances can use to find the methods they respond to. If you’ve already got objects that don’t use classes, it’s possible to make objects that do use classes by giving each object a class object. You need somewhere to hold the instance variables for an object, and it happens that objects are good for that too.

More useful to notice is that objects are really just a way to do late binding of functions to their names. It doesn’t really matter what rules you use, as long as the result is a map of names to functions you’ve got yourself an object that will work with other objects.

posted by Graham at 14:41  

Friday, June 12, 2015

Mutable objects in immutable objects in object-oriented programming in functional programming in Swift

I didn’t realise this at the time, the previous entry wasn’t the last Objective-Swift post.

The inheritance mechanism in ObjS is prototypical, meaning that an object inherits from a single other object rather than getting its behaviour from a class. This is the same system that Self and languages that, um, inherit its approach use.

This form of inheritance gives us two capabilities: decorating an object by attaching new methods, or updating an object by shadowing existing methods. And that means that setting a variable can be mimicked by returning an object where the accessor for that variable has been overridden. So in fact the objects in this system won’t be mutable at all, but they will have mutators that return replacement values.

It sounds weird, but there are reasons to really do this. In Postscript, you can mimic variables by creating named functions that just push a value onto the stack. Rather than mutating the data, you “set” the variable by rebinding the name to a function that pushes the updated value.

Digression: updating the dispatch system

In rewriting setters to be immutable I also noticed it was possible to consolidate the “accessor” and “mutator” implementation types into a single type, using variadic arguments. I have genuinely no idea why I didn’t realise that before, when the type of an ObjC method is usually expected to be (id, SEL, id...) -> id.

enum IMP {
  case method((Selector->IMP, Selector, Selector->IMP...)->(Selector->IMP)?)
  case asInteger((Selector->IMP, Selector, Selector->IMP...)->Int?)
  case methodMissing((Selector->IMP, Selector, Selector->IMP...)->(Selector->IMP)?)
  case description((Selector->IMP, Selector, Selector->IMP...)->String?)

The asInteger and description types gain variadic arguments but still need to be present so you can exit the O-O type system and get back to Swift types. For the moment, methodMissing is still modelled as a separate case in the enumeration, even though it has the same type as a regular method.

Mutation as a function

Given an object, a selector to override, and the replacement value, return a new object that will return that value when messaged with that selector.

infix operator ☞ {}

func mutate(receiver: Object, selector: Selector, value:Object) -> Object {
  return { _cmd in
    switch (_cmd) {
    case selector:
      return .method({ _ in return value })
      return receiver(_cmd)

func ☞(message:(receiver: Object?, selector: Selector), value:Object) -> Object? {
  if let receiver = message.receiver {
    return mutate(receiver, message.selector, value)
  } else {
    return nil

Taking the Point objects from the further advances post, but deleting their mutators, this can be used to make updated objects.

let p = Point(3, 4, o)
📓(p) // (3,4)
let p2 = (p,"x")☞(Integer(1,o))
📓(p2) // (1,4)

Mutation as a method

The same function can be used in the implementation of an Objective-Swift method. Here’s the setY: method on Points:

  return IMP.method({ (this, aSelector, args : Object...) in
    return (this, "y")☞args[0]

Now a bit of notation to make calling mutator methods easier (I’m starting to run out of reasonable symbols):

infix operator ✍ {}

func ✍(message:(receiver:Object?, selector:Selector), value:Object) -> Object? {
  if let imp = message.receiver..message.selector {
    switch imp {
    case .method(let f):
      return f(message.receiver!, message.selector, value)
      return nil
  } else {
    return nil


let p3 = (p2, "setY:")✍(Integer(42, o))
📓(p3) // (1,42)

Fork me

I have put the current playground (which is written for the Swift 1.2 compiler, because I’m risk averseold fashioned) on GitHub.

posted by Graham at 06:24  

Sunday, June 7, 2015

Finishing the ObjS story

This gist shows the result of doing the self-threading talked about at the end of the last post. Each method implementation takes an object pointer and a selector name, just like in the real world.

That’s enough Objective-Swift for me. Yes, more could be done (mostly defining a preprocessor to make the syntax more regular) but my goal was to understand the definition of Smalltalk-style—or maybe Self-style—objects in a functional programming environment, and I think I’m there. For now.

posted by Graham at 02:36  
Next Page »

Powered by WordPress