Thursday, January 10, 2019

Objective-Smalltalk on Linux via GNUstep and Docker

Although Objective-Smalltalk's architectural orientation should be an ideal fit for The Cloud™, this has been largely theoretical in recent times as Objective-Smalltalk only ran on macOS and iOS.

Having used both GNUstep and Cocotron to port, for example, MusselWind to Linux in the past, I knew this wasn't an insurmountable probl...er opportunity. However, dealing with VMs and OSes, and configurations getting everything to compile was always painful, and usually not reproducible.

Enter Docker for Mac. I had obviously heard quite a bit about Docker, but so far never had an opportunity to actually try it out in anger. Well, maybe not "anger", more "mild chagrin", because Docker is not really meant for running Linux binaries on your Mac. However, it does that job really, really well. Instead of futzing around with VMs, dealing with special guest OS tools in order to get window sizes to match, Retina not working, displays not resizing etc. you just get a login onto a Linux "box" right in your Terminal window, no muss no fuss. Nice. And mounting directories from the Mac is also trivial. Niiiice.

The other part that makes this different is the whole idea of reproducibility via Dockerfiles. Because a container is at least conceptually ephemeral (practically you can keep it around for quite a bit), you don't capture your knowledge in the state of the VM you are working on. Instead, you accumulate the knowledge in the Dockerfile(s) used to construct your image.

The Dockerfile for creating a GNUstep image/container that is capable of compiling + running Objective-Smalltalk can be found here:

https://github.com/mpw/MPWFoundation/tree/master/GNUstep/gnustep-combined
The main Dockerfile loads first loads a bunch of packages via apt-get:
FROM ubuntu

ENV LC_ALL en_US.UTF-8
ENV LANG en_US.UTF-8
ENV TZ 'Europe/Berlin'
RUN ln -snf /usr/share/zoneinfo/$TZ /etc/localtime && echo $TZ > /etc/timezone


RUN apt-get update && apt-get install -y \
    git \
    make \
    ssh \
    sudo \
    curl \
    inetutils-ping \
    vim build-essential  \
    clang llvm libblocksruntime-dev libkqueue-dev libpthread-workqueue-dev libxml2-dev cmake \
    libffi-dev \
    libreadline6-dev \
    libedit-dev \
    libmicrohttpd-dev \
    gnutls-dev 


RUN useradd -ms /bin/bash gnustep

COPY install-gnustep-clang /home/gnustep/
RUN chmod u+x /home/gnustep/install-gnustep-clang
RUN /home/gnustep/install-gnustep-clang  

COPY bashrc /home/gnustep/.bashrc
COPY profile /home/gnustep/.profile
COPY bashrc /root/.bashrc
COPY profile /root/.profile
COPY bashrc /.bashrc
COPY profile /.profile

COPY build-gnustep-clang /home/gnustep/build-gnustep-clang
RUN  mkdir -p /home/gnustep/patches/libobjc2-1.8.1/
COPY patches/libobjc2-1.8.1/objcxx_eh.cc /home/gnustep/patches/libobjc2-1.8.1/objcxx_eh.cc

RUN chmod u+x /home/gnustep/build-gnustep-clang
RUN /home/gnustep/build-gnustep-clang  


COPY build-gnustep-clang /home/gnustep/build-gnustep-clang
RUN  mkdir -p /home/gnustep/patches/libobjc2-1.8.1/
COPY patches/libobjc2-1.8.1/objcxx_eh.cc /home/gnustep/patches/libobjc2-1.8.1/objcxx_eh.cc

RUN chmod u+x /home/gnustep/build-gnustep-clang
RUN /home/gnustep/build-gnustep-clang  

CMD ["bash"]

It adds a user "gnustep", then runs a script that will downloads specific version of the gnustep and libobjc2 sources using a script, patches one of those sources which wouldn't compile for me and finally builds and installs the whole thing using another script, both adapted from Tobias Lensing's post.


#!/bin/bash
#


cd /home/gnustep/

echo Installing gnustep-make
export CC=clang
echo compiler is $CC

tar zxf gnustep-make-2.7.0.tar.gz
cd gnustep-make-2.7.0
./configure
make install
cd ..

echo 
echo 
echo ======================
echo Installing libobjc2


tar zxf libobjc2-1.8.1.tar.gz
cp patches/libobjc2-1.8.1/* libobjc2-1.8.1/
cd libobjc2-1.8.1
mkdir Build
cd Build
# cmake -DCMAKE_C_COMPILER=clang -DCMAKE_CXX_COMPILER=clang -DTESTS=OFF -DLLVM_OPTS=OFF  ..
cmake -DTESTS=OFF .. 
make install
cd ../..


cd gnustep-make-2.7.0
make clean
./configure --with-library-combo=ng-gnu-gnu
make install
cd ..

source /usr/local/share/GNUstep/Makefiles/GNUstep.sh
tar zxf gnustep-base-1.25.1.tar.gz 
cd gnustep-base-1.25.1
./configure
make installn
cd ..

echo Installation script finished successfully

One of the tricky bits about this is that you need to install the gnustep-make package twice, first to get libobjc2 to install, the second time with libobjc2 installed so all the other packages find the right runtime. The apt-get packages did not work for me, because I needed newer compiler/runtime features.

Once you have the image, you can start it up and log into it. I then su -l to the gnustep account and work with the MPWFoundation, ObjectiveSmalltalk and ObjectiveHTTPD mounted from my local filesystem, rather than having separate copies inside the container.

Not everything is ported, but basic expressions work, as does messaging back and forth between Objective-Smalltalk and Objective-C, Higher Order Messaging, etc. Considering some of the runtime trickery involved, I was surprised how straightforward it was to get this far.

In the future, I expect to also build a runtime image that has the libraries and executable pre-built.

Friday, January 4, 2019

Swifter Sieving of Primes with Software ICs

I've been working much more on Objective-Smalltalk again, which is great, but that also made me think more intently on the motivations, because a lot of what is there is probably not quite obvious without knowing why and how it got there.

One of the obvious motivations has been Objective-C, and in particular the notion of Software-ICs, components that are connected via dynamic messages. This is actually an instance of the Scripted Components (pdf) pattern, with the interesting twist that unlike most of the instances of this pattern, there is only a single programming language for both the scripts and the components, that language being Objective-C.

In a sense, Objective-C is not really a language, it is middleware with some language features. And therein lies much confusion, because people try to use it as "just" a language. In particular, they try to use the "Objective" parts as an algorithmic programming language, something it is eminently unsuited for. This is what the "C" part is for, which is somewhere around 90% of the actual language.

To back off for a bit, a Scripted Component system is one where you have components that are written in one language, often C or C++, that are then glued together using a more dynamic scripting language, for example Unix shell, Visual Basic. One of the more extreme examples of this pattern is computational steering of supercomputer applications using Tcl(!). Which brings up the point of performance: one of the interesting aspects of the Scripted Components pattern is that it combines the excellent performance of the component language with the flexibility and interactivity of the scripting language.

Which brings me back to Objective-C, almost. No one at the supercomputer centers that used Tcl for steering would have had the idea of implementing their actual computation in Tcl. No, implementing the components is what you use C or C++ or maybe FORTRAN for. You then combine, parametrise and maybe invoke those components from the scripting language.

Yet when it comes to Objective-C, that is exactly what people do: they implement the algorithmic parts in the scripting/middleware part of Objective-C and then wonder why it comes out looking like the following (taken from Vincent's post):


NSArray<NSNumber *> *sieve(NSArray<NSNumber *> *sorted) {
  if ([sorted count] == 0) { return [NSArray new]; }
  NSUInteger head = sorted[0].unsignedIntegerValue;
  NSArray *tail = [sorted subarrayWithRange:NSMakeRange(1, sorted.count - 1)];
  NSIndexSet *indexes = [tail indexesOfObjectsPassingTest:^BOOL(NSNumber *element, NSUInteger idx, BOOL *stop) {
    return element.unsignedIntegerValue % head > 0;
  }];
  NSArray *sieved = [tail objectsAtIndexes:indexes];
  return [@[@(head)] arrayByAddingObjectsFromArray:sieve(sieved)];
}

NSMutableArray *numbers = [NSMutableArray new];
for (NSUInteger i = 2; i <= 100; i++) {
  [numbers addObject: @(i)];
}
NSArray *primes = sieve(numbers);
NSLog(@"%@ -> %@", numbers, primes);

Yes, this code doesn't make sense. Or it makes about as much sense as implementing your computational fluid dynamics simulation in Tcl and then scripting it using C. And yes, the Swift code definitely looks a bit nicer:


func sieve(_ sorted: [Int]) -> [Int] {
	guard !sorted.isEmpty else { return [] }
	let (head, tail) = (sorted[0], sorted[1..&now lt;sorted.count])
	return [head] + sieve(tail.filter { $0 % head > 0 })
}

let numbers = Array(2...100)
let primes = sieve(numbers)
print("\(numbers) -> \(primes)")

The first thing I noticed was that I couldn't even tell what this was doing, it took me a bit of close reading of the code to realise that my confusion was due to the fact that although this does compute primes, it isn't actually the Sieve of Eratosthenes!

The hallmark of the Sieve is that it computes primes while avoiding expensive division (and multiplication by anything other than 2, a simple shift left) operations. It does this by allocating an array with the candidate numbers (it starts from 2, because all numbers are multiples of 1) and then eliminating any known non-primes (multiples of some other number) by stepping through the array at a certain step-size. To eliminate all multiples of 2, step through the array with a step size of 2. To eliminate all multiples of 3, step through the array with a step size of 3, and so on. This was great on small microcomputers that did not have multiplication or division operations in hardware.

The algorithm presented here just checks all remaining numbers if they are divisible by the current number using a modulo operation.

But the fact that this is the wrong algorithm wasn't really what caught my eye, rather that was the unidiomatic and to me, quite frankly, rather bizarre way of using Objective-C: this example uses Objective-C Foundation objects to implement algorithms on integers.

It is not surprising that this code looks weird, because it is. Objective-C is a hybrid language intended for the construction and connection of Software-ICs. You implement the algorithms inside the Software-IC using C and then package it up (and connect) with the dynamic messaging provided by the "Objective" part.

So let's do that! First, we grab a C implementation of the (real) Sieve of Eratosthenes algorithm, for example from the first Duck Go Go search result here:


#include <stdio.h>

#define LIMIT 1500000 /*size of integers array*/
#define PRIMES 100000 /*size of primes array*/

int main(){
    int i,j,numbers[LIMIT];
    int primes[PRIMES];

    /*fill the array with natural numbers*/
    for (i=0;i<limit;i++){
        numbers[i]=i+2;
    }

    /*sieve the non-primes*/
    for (i=0;i<limit;i++){
        if (numbers[i]!=-1){
            for (j=2*numbers[i]-2;j<limit;j+=numbers[i])
                numbers[j]=-1;
        }
    }

    /*transfer the primes to their own array*/
    j = 0;
    for (i=0;i<limit&&j<primes;i++)
        if (numbers[i]!=-1)
            primes[j++] = numbers[i];

    /*print*/
    for (i=0;i<primes;i++)
        printf("%dn",primes[i]);

return 0;
}

This somewhat longer than the previous examples, but it does have the distinct advantage of actually being a Sieve of Eratosthenes :-). The way it works is that it first intialises an array of size N with the integers from 1 to N. The Sieve then knocks out multiples of n for n in 1 to N. The "knocking out" is performed by setting the array element to -1. Finally, all the non-negative numbers are retrieved from the array. These are the primes, which are then printed.

Sine Objective-C is a strict superset of C, we could simply use this code as-is. However, it does lack some conveniences, for example the array sizes are fixed, the code isn't reusable and for example printing is very manual. So using the idea of the Software-IC, we notice that an array of integers is the central data structure here. Apple's Foundation doesn't provide such a beast, but that isn't a big deal, we can easily write one ourselves, or more precisely reuse the one provided in MPWFoundation.

As this is going to be running all over the array, we probably want to break open the encapsulation boundary of the Software-IC and implement the core of the algorithm as an extension, er, category of MPWIntArray.

Another slight improvement is breaking the Sieve algorithm up into smaller, named pieces that tell you what is going on, and using conveniences such as -select: to filter the results. Printing of the contents is also something that is provided.


@import MPWFoundation;

@implementation MPWIntArray(primes)

-(void)knockoutMultiplesOf:(int)n
{
    int *numbers=data;
    if (n > 0){
       for (int j=2*n-2,max=[self count];j<max;j+=n) {
           numbers[j]=-1;
       }
    }
}

-(void)sievePrimes
{
    for (int i=0,max=[self count];i<max;i++){
        [self knockoutMultiplesOf:data[i]];
    }
}

@end

int main(int argc, char *argv[])
{
    int n=argc > 1 ? atoi(argv[1]) : 100000;
    MPWIntArray *numbers=[[@(2) to:@(n-2)] asArray];
    [numbers sievePrimes];

    MPWIntArray *primes = [numbers select:^(int potentialPrime) {
        return (BOOL)(potentialPrime > 0);
    }];
    printf("primes: %s\n",[[primes description] UTF8String]);
    printf("number of primes: %d\n",[primes count]);
}

One of the benefits of the Software-IC or Scripted Components style is performance, otherwise you wouldn't want to use it in supercomputer settings. In this particular case I ran the Swift version against the Software-IC version (I didn't bother with the original Objective-C version). The performance difference is so remarkable that it was actually difficult to find values for the N parameter that gave at least somewhat reasonable/comparable results for both variants:
N Swift Sieve Software-IC Sieve Ratio
100000 0,501 0,006 83,5
200000 1,78 0,007 254,3
300000 3,78 0,008 472,5
400000 6,43 0,009 714,4
500000 9,74 0,010 974,0
Sieve times
I couldn't go much higher than N=500,000 with the Swift version because at N=500,000 it was already using around 8GB of memory and rising quickly. At that point you start to see paging activity on a reasonably busy machine, particularly one with Xcode open and I didn't want to get my machine "benchmark-clean". At those same N values, the Software-IC version isn't really getting started yet, the execution time actually being dominated by startup costs and random fluctuations. In fact, launching it with N=1 also takes 6-8ms the same as for N=500,000.

So yes, using Swift to do computations is certainly a better choice than abusing the middleware part of Objective-C to do those computations. On the other hand, used properly for constructing a Software-IC and then providing an interface to it, Objective-C does quite well. Which doesn't mean we couldn't do better for both parts: yes, somewhat better algorithmics bute more importantly better middleware and less muddle about which is which. It shouldn't come as a complete shock that that is the (rough) idea behind Objective-Smalltalk, but more on that later.

UPDATE:
My little post triggered a small twitter discussion that was really much better than the post itself. Although my point was really mostly about the scripted components pattern and how it relates to Objective-C and its Software-ICs, I focused a bit too much on the performance aspect (occupational hazard). It also comes off a bit too much as "Swift vs. Objective-C", so to make that clear: the Objective-C code initially presented is probably slowest, and I am reasonably certain that you can write a C-like Sieve using Swift with roughly comparable performance.

For me, the bigger point was that this code was a good illustration of the misunderstanding and misapplication of Objective-C. I am also decidedly not saying that this misapplication is due ignorance of the people doing the misapplication, I think it has to do with the fact that the tension between scripted coomponents and unified language is something we haven't figured out yet.

Anyway, Helge managed to put the point very succinctly:

Also insightful as alway, Joe Groff:

And a little bit of "hey, I didn't know that":

And last not least: apologies again to Vincent for picking on him, just a little bit :-)

Sunday, December 30, 2018

UIs Are Not Pure Functions of the Model - React.js and Cocoa Side by Side

When I first saw React.js, I had a quick glance and thought that it was cool, they finally figured out how to do a Cocoa-like MVC UI framework in JavaScript.

Of course, they could have just used Cappuccino, but "details". Some more details were that their version of drawRect: was called render() and returned HTML instead of drawing into a graphics context, but that's just the reality of living inside a browser. And of course there was react-canvas.

Overall, though, the use of a true MVC UI framework seemed like a great step forward compared to directly manipulating the DOM on user input, at least for actual applications.

Imagine my surprise when I learned about React.native! It looked like they took what I had assumed to be an implementation detail as the main feature. Looking a little more closely confirmed my suspicions.

Fortunately, the React.js team was so kind as to put their basic ideas in writing: React - Basic Theoretical Concepts (also discussed on HN) ). So I had a look and after a bit of reading decided it would be useful to do a side-by-side comparison with equivalents of those concepts in Cocoa as far as I understand them.


React

Cocoa

Transformation

The core premise for React is that UIs are simply a projection of data into a different form of data. The same input gives the same output. A simple pure function.

function NameBox(name) {
  return { fontWeight: 
          'bold', labelContent: name };
}

Transformation

A core premise of Cocoa, and MVC in general, is that UIs are a projection of data into a different form of data, specifically bits on a screen. The same input gives the same output. A simple method:
 -(void)drawRect:(NSRect)aRect  {
	...
}
Due to the fact that screens and the bits on them are fairly expensive, we use the screen as an accumulator instead of returning the bits from the method.

We do not make the (unwarranted) assumption that this transformation can or should be expressed as a pure function. While that would be nice, there are many reasons why this is not a good idea, some pretty obvious.

Abstraction

You can't fit a complex UI in a single function though. It is important that UIs can be abstracted into reusable pieces that don't leak their implementation details. Such as calling one function from another.

function FancyUserBox(user) {
  return {
    borderStyle: '1px solid blue',
    childContent: [
      'Name: ',
      NameBox(user.firstName + ' ' +
user.lastName)
    ]
  };
}
{ firstName: 'Sebastian', 
   lastName: 'Markbåge' } ->
{
  borderStyle: '1px solid blue',
  childContent: [
    'Name: ',
    { fontWeight: 'bold',
    labelContent: 'Sebastian Markbåge' }
  ]
};

Abstraction

Although it is be possible to render an entire UI in a single View's drawRect:: method, and users of NSOpenGLView tend to do that, it is generally better practice to split complex UIs into reusable pieces that don't leak their implementation details.

Fortunately we have such reusable pieces, they are called objects, and we can group them into classes. Following the MVC naming conventions, we call objects that represent UI views, in Cocoa they are instance of NSView or its subclasses, in CocoaTouch the common superclass in called UIView.

Composition

To achieve truly reusable features, it is not enough to simply reuse leaves and build new containers for them. You also need to be able to build abstractions from the containers that compose other abstractions. The way I think about "composition" is that they're combining two or more different abstractions into a new one.

function FancyBox(children) {
  return {
    borderStyle: '1px solid blue',
    children: children
  };
}

function UserBox(user) {
  return FancyBox([
    'Name: ',
    NameBox(user.firstName + ' ' +
    user.lastName)
  ]);
}

Composition

To achieve truly reusable features, it is not enough to simply reuse leaves and build new containers for them. You also need to be able to build abstractions from the containers that compose other abstractions. The way I think about "composition" is that they're combining two or more different abstractions into a new one.

Examples of this are the NSScrollView, which composes the actual scrollers, themselves composed of different parts, a NSClipView to provide a window onto the user-provided contentView.

Other examples are NSTableViews coordinating their columns, rows, headers and the system- or user-provided Cells.

State

A UI is NOT simply a replication of server / business logic state. There is actually a lot of state that is specific to an exact projection and not others. For example, if you start typing in a text field. That may or may not be replicated to other tabs or to your mobile device. Scroll position is a typical example that you almost never want to replicate across multiple projections.

We tend to prefer our data model to be immutable. We thread functions through that can update state as a single atom at the top.

function FancyNameBox(user, likes,
  onClick) {
  return FancyBox([
    'Name: ', NameBox(user.firstName + ' ' +
  user.lastName),
    'Likes: ', LikeBox(likes),
    LikeButton(onClick)
  ]);
}

// Implementation Details

var likes = 0;
function addOneMoreLike() {
  likes++;
  rerender();
}

// Init

FancyNameBox(
  { firstName: 'Sebastian', 
   lastName: 'Markbåge' },
  likes,
  addOneMoreLike
);

NOTE: These examples use side-effects to update state. My actual mental model of this is that they return the next version of state during an "update" pass. It was simpler to explain without that but we'll want to change these examples in the future.

State

A UI is NOT simply a replication of server / business logic state. There is actually a lot of state that is specific to an exact projection and not others. For example, if you start typing in a text field. That may or may not be replicated to other tabs or to your mobile device. Scroll position is a typical example that you almost never want to replicate across multiple projections.

Fortunately, the view objects we are using already provide exactly this UI-specific state, so yay objects.

Memoization

Calling the same function over and over again is wasteful if we know that the function is pure. We can create a memoized version of a function that keeps track of the last argument and last result. That way we don't have to reexecute it if we keep using the same value.

function memoize(fn) {
  var cachedArg;
  var cachedResult;
  return function(arg) {
    if (cachedArg === arg) {
      return cachedResult;
    }
    cachedArg = arg;
    cachedResult = fn(arg);
    return cachedResult;
  };
}

var MemoizedNameBox = memoize(NameBox);

function NameAndAgeBox(user, currentTime)
 {
  return FancyBox([
    'Name: ',
    MemoizedNameBox(user.firstName +
     ' ' + user.lastName),
    'Age in milliseconds: ',
    currentTime - user.dateOfBirth
  ]);
}

Memoization

Calling the same method over and over again is wasteful.

So we don't do that.

First, we did not start with the obviously incorrect premise that the UI is a simple "pure" function of the model. Except for games, UIs are actually very stable, more stable than the model. You have chrome, viewers, tools etc. What is a (somewhat) pure mapping from the model is the data that is displayed in the UI, but not the entire UI.

So if we don't make the incorrect assumption that UIs are unstable (pure functions of model), then we don't have to expend additional and fragile effort to re-create that necessary stability.

In terms of optimizing output, this is also handled within the model, rather than in opposition to it: views are stable, so we keep a note of which views have collected damage and need to be redrawn. The application event loop coalesces these damage rectangles and initiates an optimized operation: it only redraws views whose bounds intersect the damaged region, and also passes the rectangle(s) to the drawRect:: method. (That's why it's called drawRect::).

Lists

Most UIs are some form of lists that then produce multiple different values for each item in the list. This creates a natural hierarchy.

To manage the state for each item in a list we can create a Map that holds the state for a particular item.

function UserList(users, likesPerUser,
 updateUserLikes) {
  return users.map(user => FancyNameBox(
    user,
    likesPerUser.get(user.id),
    () => updateUserLikes(user.id, 
likesPerUser.get(user.id) + 1)
  ));
}

var likesPerUser = new Map();
function updateUserLikes(id, likeCount) {
  likesPerUser.set(id, likeCount);
  rerender();
}

UserList(data.users, likesPerUser,
            updateUserLikes);

NOTE: We now have multiple different arguments passed to FancyNameBox. That breaks our memoization because we can only remember one value at a time. More on that below.

Lists

Most UIs are some form of lists that then produce multiple different values for each item in the list. This creates a natural hierarchy.

Fortunately there is nothing to do here, the basic hierarchical view model already takes care of it. There are specific view classes for lists, but there is nothing special about them in terms of the conceptual or implementation model.

Continuations

Unfortunately, since there are so many lists of lists all over the place in UIs, it becomes quite a lot of boilerplate to manage that explicitly.

We can move some of this boilerplate out of our critical business logic by deferring execution of a function. For example, by using "currying" (bind in JavaScript). Then we pass the state through from outside our core functions that are now free of boilerplate.

This isn't reducing boilerplate but is at least moving it out of the critical business logic.

function FancyUserList(users) {
  return FancyBox(
    UserList.bind(null, users)
  );
}

const box = FancyUserList(data.users);
const resolvedChildren =
     box.children(likesPerUser,
        updateUserLikes);
const resolvedBox = {
  ...box,
  children: resolvedChildren
};

Continuations

Fortunately, it doesn't matter how many lists of lists there are all over the place in UIs, since our composition mechanism actually works for this use case.

State Map

We know from earlier that once we see repeated patterns we can use composition to avoid reimplementing the same pattern over and over again. We can move the logic of extracting and passing state to a low-level function that we reuse a lot.

function FancyBoxWithState(
  children,
  stateMap,
  updateState
) {
  return FancyBox(
    children.map(child => child.continuation(
      stateMap.get(child.key),
      updateState
    ))
  );
}

function UserList(users) {
  return users.map(user => {
    continuation:
      FancyNameBox.bind(null, user),
    key: user.id
  });
}

function FancyUserList(users) {
  return FancyBoxWithState.bind(null,
    UserList(users)
  );
}

const continuation =
     FancyUserList(data.users);
continuation(likesPerUser,
 updateUserLikes);

State Map

Don't need it.

(Just how many distinct mechanism do we have now for re-introducing state? At what point do we revisit our initial premise that UIs are pure functions of the model??)

Memoization Map

Once we want to memoize multiple items in a list memoization becomes much harder. You have to figure out some complex caching algorithm that balances memory usage with frequency.

Luckily, UIs tend to be fairly stable in the same position. The same position in the tree gets the same value every time. This tree turns out to be a really useful strategy for memoization.

We can use the same trick we used for state and pass a memoization cache through the composable function.

function memoize(fn) {
  return function(arg, memoizationCache) {
    if (memoizationCache.arg === arg) {
      return memoizationCache.result;
    }
    const result = fn(arg);
    memoizationCache.arg = arg;
    memoizationCache.result = result;
    return result;
  };
}

function FancyBoxWithState(
  children,
  stateMap,
  updateState,
  memoizationCache
) {
  return FancyBox(
    children.map(child =>
    child.continuation(
      stateMap.get(child.key),
      updateState,
      memoizationCache.get(child.key)
    ))
  );
}

const MemoizedFancyNameBox =

      memoize(FancyNameBox);

Memoization Map

Huh?

Seriously?

Algebraic Effects

It turns out that it is kind of a PITA to pass every little value you might need through several levels of abstractions. It is kind of nice to sometimes have a shortcut to pass things between two abstractions without involving the intermediates. In React we call this "context".

Sometimes the data dependencies don't neatly follow the abstraction tree. For example, in layout algorithms you need to know something about the size of your children before you can completely fulfill their position.

Now, this example is a bit "out there". I'll use Algebraic Effects as proposed for ECMAScript. If you're familiar with functional programming, they're avoiding the intermediate ceremony imposed by monads.

function ThemeBorderColorRequest() 
{ }

function FancyBox(children) {
  const color = raise 
    new ThemeBorderColorRequest();
  return {
    borderWidth: '1px',
    borderColor: color,
    children: children
  };
}

function BlueTheme(children) {
  return try {
    children();
  } catch effect
     ThemeBorderColorRequest -> 
     [, continuation] {
    continuation('blue');
  }
}

function App(data) {
  return BlueTheme(
    FancyUserList.bind(null, data.users)
  );
}

Algebraic Effects

It turns out that it is kind of a PITA to pass every little value you might need through several levels of abstractions....

So don't do that.

This is another reason why it's advantageous to have a stable hierarchy of stateful objects representing your UI. If you need more context, you just ask around. Ask your parent, ask your siblings, ask your children, they are all present. Again, no special magic needed.


So that was the comparison. I have to apologise for getting somewhat less detail-oriented near the end, but the level of complexity just started to overwhelm me. Add to that, for React.native, the joy of having to duplicate the entire hierarchy of view classes, just to have the "components" generate not-quite-temporary temporary views that than generate layers that draw the actual UI. Maybe there's one too many layers. Or two.

The idea of UI being a pure function of the model seems so obviously incorrect, and leads to such a plethora of problems, that it is a bit puzzling how one could come up with it in the first place, and certainly how one would stick with it in face of the avalanche of problems that just keeps coming. A part of this is certainly the current unthinking infatuation with functional programming ideas. These ideas are broadly good, but not nearly as widely or universally applicable as some of their more starry-eyed proponents propose (I hesitate to use the word "think" in this context).

Another factor is the the usefulness of immediate-mode graphics, compared to retained-state graphics. This is actually an interesting topic by itself, IMHO, one of those eternal circles where we move from a fully retained model such as the early GKS or laterr Phigs to immedate drawing models such as Postscript, Quartz, und OpenGL, only to then re-invent the retained model (sort of) with things like CoreAnimation, Avalon and, of course, the DOM (and round and round we go). Cocoa's model represents a variable approach, where you can mix-and-match object-oriented and immediate-mode drawing as you see fit. But more on that later.

Last not least, it's probably not entirely coincidental that this idea was hatched for Facebook and Instagram feed applications. Similar to games, these sorts of apps have displays that really are determined mostly by their "model", the stream of data coming from their feed. I am not convinced that feed application generalizes well to application.

Anyway, for me, this whole exercise has actually motivated me to start using react.js a little. I still think that Cappuccino is probably the better, less confused framework, but it helps to know about what the quasi-mainstream is doing. I also think that despite all the flaws, react.js and react.native are currently eating native development's lunch. And that's certainly interesting. Stay tuned!

UPDATE:
Dan Abramov responds:

I think you’re overfocusing on the “pure” wording and theoretical definitions over practical differences.
To elaborate a bit, React components aren’t always “pure” in strict FP sense of the word. They’re also not always functions (although we’re adding a stateful function API as a preferred alternative to classes soon). Support for local state and side effects is absolutely a core feature of React components and not something we avoid for “purity”.

I added a PR to remove the misleading "pure" from the concepts page.

Sunday, December 23, 2018

A Minimal Test Runner

A long time ago when I was working a MPWTest, "The simplest Objective-C Unit Test Framework that could possibly work...", I had a brief chat with Kent Beck about it, and one of the things he said was that everyone should build their own unit test "framework".

Why the scare quotes?

If your testing framework is actually a framework, it's probably too big. I recently started porting MPWFoundation and Objective-Smalltalk to GNUstep again, in order to get it running In the Cloud™. In order to see how it's going, it's probably helpful to run the tests.

Initially, I needed to test some compiler issues with such modern amenities as keyed subscripting of dictionaries:


#import <Foundation/Foundation.h>

int main( int argc, char *argv[] ) {
  MPWDictStore *a=[MPWDictStore store];
  a[@"hi"]=@"there";
  NSLog(@"hi: %@",a[@"hi"]);
  return 0;

}

Once that was resolved with the help of Alex Denisov, I wanted to minimally run some tests, but the idea of first getting all of MPWTest to run wasn't very appealing. So instead I just did the simplest thing that could possible work:
static void runTests()
{
  int tests=0;
  int success=0;
  int failure=0;
  NSArray *classes=@[
    @"MPWDictStore",
    @"MPWReferenceTests",
  ];

  for (NSString *className in classes ) {
    id testClass=NSClassFromString( className );
    NSArray *testNames=[testClass testSelectors];
    for ( NSString *testName in testNames ) {
      SEL testSel=NSSelectorFromString( testName );
      @try {
        tests++;
        [testClass performSelector:testSel];
        NSLog(@"%@:%@ -- success",className,testName);
        success++;
      } @catch (id error)  {
        NSLog(@"%@:%@ == failure: %@",className,testName,error);
        failure++;
      }
    }

  }
  printf("\033[91;3%dmtests: %d total, %d successes %d failures\033[0m\n",
         failure>0 ? 1:2,tests,success,failure);
}

That's it, my minimal testrunner. With hard-coded list of classes to test. In a sense, that is the entire "test framework", the rest just being conventions followed by classes that wish to be tested.

And of course MPWTests's slogan was a bit...optimistic.

Sunday, November 11, 2018

Refactoring Towards Language

When implementing MVC in iOS and macOS, one common pattern is to use NSNotification to implement the notification that the model has changed and the view should redraw itself. This is a good pattern, as that is how MVC is intended to work, but it does lead to quite a bit of boilerplate in this incarnation.

Specifically, you typically have some version of the following code in one of the initialisation methods of your ViewControllers, which play the MVC role of the View in Cocoa and Cocoa Touch.


- (void)viewDidLoad
{
	...
    [[NSNotificationCenter defaultCenter] addObserver:self
                                             selector:@selector(modelDidChange:)
                                                 name:MPWAppNotificationModelDidChange
                                               object:nil];
	...
}

Refactor I

That's all good, except that you tend to repeat that code in every single ViewController, and there are usually quite a few of them. So one way of avoiding all that duplication is to refactor by extracting the duplicated functionality into a method.
- (void)subscribeToModelDidChangeNotification
{
    [[NSNotificationCenter defaultCenter] addObserver:self
                                             selector:@selector(modelDidChange:)
                                                 name:MPWAppNotificationModelDidChange
                                               object:nil];
}


- (void)unsubscribeFromModelDidChangeNotification
{
    [[NSNotificationCenter defaultCenter] removeObserver:self
                                                    name:MPWAppNotificationModelDidChange
                                                  object:nil];
}

- (void)subscribeToModelWasDeletedNotification
{
    [[NSNotificationCenter defaultCenter] addObserver:self
                                             selector:@selector(modelDidChange:)
                                                 name:MPWAppNotificationModelWasDeleted
                                               object:nil];
}


- (void)unsubscribeFromModelWasDeletedNotification
{
    [[NSNotificationCenter defaultCenter] removeObserver:self
                                                    name:MPWAppNotificationModelWasDeleted
                                                  object:nil];
}
...

Refactor II

The interesting thing that happens when you remove duplication is that it will often reveal more duplication. In particular, if you look at more of these, you will notice that the method bodies are largely identical. You always send a message to the defaultCenter of the NSNotificationCenter class, you pretty much always add yourself as the Observer, and I've rarely seen the object: parameter used. The only things that vary are the selector to send and the name of the notification.
    [[NSNotificationCenter defaultCenter] addObserver:self
                                             selector: <some selector>
                                                 name: <some notification>
                                               object:nil];


So yet another classic case for refactoring by extracting a helper method that encapsulates the things that do not change and takes the things that do vary as arguments.
-(void)subscribeToNotification:(NSString *)notificationName usingSelector:(SEL)selectorName
{
    [[NSNotificationCenter defaultCenter] addObserver:self
                                             selector:selectorName
                                                 name:notificationName
                                               object:nil];
}

We can also apply the same refactoring to unsubscribing.
-(void)unsubscribeFromNotification:(NSString *)notificationName
{
    [[NSNotificationCenter defaultCenter] removeObserver:self
                                                    name:notificationName
                                                  object:nil];
}

With the parameters extracted, our helper methods simplify to the following.
- (void)subscribeToModelDidChangeNotification
{
    [self subscribeToNotification: MPWAppNotificationModelDidChange usingSelector:@selector(modelDidChange:)];
}

- (void)unsubscribeFromModelDidChangeNotification
{
    [self unsubscribeFromNotification: MPWAppNotificationModelDidChange];
}

- (void)subscribeToModelWasDeletedNotification
{
    [self subscribeToNotification: MPWAppNotificationModelWasDeleted usingSelector:@selector(modelDidChange:)];
}

- (void)unsubscribeFromModelWasDeletedNotification
{
    [self unsubscribeFromNotification: MPWAppNotificationModelWasDeleted];
}

Refactor III

As happens very often when you extract code and remove duplication we discover more duplication that was previously somewhat hidden, for example because code that was too far away to really notice the duplication is now close enough together to make it more obvious. Specifically: we always define the same methods: subscribeTo<notification> and unsubscribeFrom<notification>. We also repeat the notification name in each of the method names, and also in each of the method bodies (with different prefixes/suffixes).
- (void)subscribeTo<notification-name>Notification
{
    [self subscribeToNotification: MPWAppNotification<notification-name> usingSelector:@selector(<notification-selector>:)];
}

- (void)unsubscribeFrom<notification-name>Notification
{
    [self unsubscribeFromNotification: MPWAppNotification<notification-name>];
}
- (void)<notification-selector>:(NSNotification *)notification
{
}

Up to this point, we managed to achieve our goals using plain refactoring techniques. Often, that is enough, and it’s generally a good idea to stop there, because beyond lies metaprogramming, which tends to make the code significantly more obscure. In Objective-C, we generally have runtime tricks and macro-programming using the C pre-processor (well: and code generation). In this case, I decided to give the C preprocessor a try, because I wanted things done at compile-time and the problem was parametrising parts of identifiers, i.e. string processing.

Doing some pattern matching, we have two actual “parameters", the “base” of the notification name ( for example ‘ModelDidChange’ or ‘ModelWasDeleted’ ) and the name of the method to call. So we create a Macro that takes these parameters and applies them to a template of the methods we need:


#define SUBSCRIBE_UNSUBSCRIBE_WITHMETHODNAME( name , notification, theMessage ) \
- (void)subscribeTo##name \
{\
    [self subscribeToNotification:notification usingSelector:@selector(theMessage:)];\
}\
\
- (void)unsubscribeFrom##name \
{\
    [self unsubscribeFromNotification:notification];\
}\
-(void)theMessage:(NSNotification *)notification\
{\
}\

#define SUBSCRIBE_UNSUBSCRIBE( commonName, theMessage ) SUBSCRIBE_UNSUBSCRIBE_WITHMETHODNAME( commonName##Notification, MPWAppNotification##commonName , theMessage )

The first macro has three arguments, a version of the notification name suitable for adding to the method names, the full notification name and the message name. The ‘##’ is the token pasting operator, which allows us to create new lexical tokens out of existing ones. We “need” it in this case because we have commonality we want to express that is on a sub-token, sub-identifier level.

There are a bunch of issues with this approach. First, it is pretty unreadable. You need to terminate every line with backslashes because Macro definitions can only be on a single logical line, the backslashes continue the logical line over physical lines. Dealing with compiler errors and warnings is rather tricky, because the error will be with the result of the macro expansion, which the error message will usually not contain. (You can tell the compiler to run just the pre-processor and give you the result, in case you need to debug and can’t do the macro expansion in your head…). Finally, you cannot search for the tokens that get generated by the pre-processor. So for example no command-clicking, and you have to be careful if you ever change one of the notification names.

The advantage is that you get a representation that succinctly states what you want to accomplish, without any duplicated boilerplate. No duplication also means no chance to get those duplicates wrong: the first few code samples in this post actually contain an error. (MPWAppNotificationModelWasDeleted also sends the modelDidChange: message instead of its own modelWasDeleted:) This error, almost certainly a copy-and-paste bug, was actually in the original code and had gone unnoticed for months until I tried to remove that duplication.

I don't know about you, but my eyes just glaze over when scanning large swathes of mostly duplicated code.

Anyway, with the Macros, our help methods are now defined as follows:


SUBSCRIBE_UNSUBSCRIBE( ModelDidChange, modelDidChange )
SUBSCRIBE_UNSUBSCRIBE( ModelWasDeleted, modelWasDeleted )

SUBSCRIBE_UNSUBSCRIBE( ActivityCountDidChange, activityCountDidChange )
SUBSCRIBE_UNSUBSCRIBE( ObjectIdDidChange, objectIdDidChange )
SUBSCRIBE_UNSUBSCRIBE( UserDidLogin, userDidLogin )

Note that previously we showed just two notifications, now we are showing all five, which would have been quite unwieldy before.

Refactor IV

As is typical when you remove duplication, you notice more duplication, because stuff is closer together: the two parameters are almost identical, except for capitalisation. This doesn't have to be the case, but it is a good convention to have. Alas, the pre-processor can’t change the capitalisation of strings so we are stuck.

To recap, this was a process of detecting duplication, removing that duplication using available mechanisms and then detecting more duplication, over several iterations. What then usually happens is that you either manage to remove all the duplication, or you notice that you cannot reduce duplication any further. Not being able to remove duplication typically means that you have reached limitations of your language, with metaprogramming facilities allowing you to push those limitations at least a little, and sometimes quite a bit.

This particular exploration relied on a somewhat formulaic use of NSNotificationCenter, one that always matches a notification with the same message. Since messages are already late-bound, this doesn't really present much of a restriction and seems a useful simplification, and it is a simplification that I've seen used widely in practice. The other pattern is that specific classes typically observe notifications for essentially their entire lifetime, meaning that the ability to dynamically turn notifications on and off is often not needed.

If we imagine language support for notifications (the implicit invocation architectural style), we would probably like to be able to declare notifications, declare that a class listens to a specific notification and and check conformance. This would make usage even more convenient than the macros we refactored to, while at the same time addressing the problems of the macro solution.

And of course that is what Notification Protocols became: a slight misappropriation of Objective-C and Swift Protocols to get something that is extremely close to actual language support. I can now actually declare my notifications as almost a programming-language thing (at least better than a string), and also specify the relationship between a message and that notification, which otherwise is purely lost in convention:


@protocol ModelDidChange <MPWNotificationProtocol>

-(void)modelDidChange:(NSNotifiction*)notification;

@end

I can also easily and declaratively specify that a particular class listens to a notification:
@interface NotifiedView:NSView <ModelDidChange>

@end

Not only does this remove the problems with the Macro approach, unreadability and untraceability, it is actually quite a bit better than the approach without Macros, all while being at least as compact. Last not least, notification sending is not just compact, but also obvious and at least somewhat compiler-checked:
[@protocol(ModelDidChange) notify];

This is very, very close to native language support, due to some lucky coincidences and the wise decision to make Protocols first class objects in Objective-C. It also does not match the flexibility of the NSNotificationCenter APIs, but I doubt whether that additional flexibility is actually used/useful.

Had I not experimented with removing duplication, and iterated on removing duplication, I never would have come to the point where notification protocols became an obvious solution. And now that I have notification protocols, I also have a good idea what actual language support should look like, because I've been using something pretty close.

So for me, plain old refactoring, different kinds of metaprogramming and language support all live on a continuum of improving expressiveness, and all are, or at least should be part of our feedback loops. How can we improve our language so we don't need metaprogramming for common use cases? How can we improve our metaprogramming facilities so they are sufficient and we don't feel a need for replacing them with actual language support? How can we do both, turn things that currently require metaprogramming look more like plain base-level programming while making it integrate better than metaprogramming solutions?

That, Detective, is the right question. Program terminated

Wednesday, October 31, 2018

Even Easier Notification Sending with Notification Protocols in Objective-C

Having revisited Notification Protocols in order to ensure they work with Swift, I had another look at how to make them even more natural in Objective-C.

Fortunately, I found a way:


[@protocol(ModelDidChange) notify:@"Payload"];
This will send the ModelDidChange notification with the object parameter @"Payload". Note that the compiler will check that there is a Protocol called ModelDidChange and the runtime will verify that it is an actual notification protocol, raising an exception if that is not true. You can also omit the parameter:
[@protocol(ModelDidChange) notify];
In both cases, the amount of boilerplate or semantic noise is minimised, whereas the core of what is happening is put at the forefront. Compare this to the traditional way:
[[NSNotificationCenter defaultCenter] postNotificationName:@"ModelDidChange" object:@"Payload"]
Here, almost the entire expression is noise, with the relevant pieces being buried near the end of the expression as parameters. No checking is (or can be) performed to ensure that the argument string actually refers to a notification name.

Of course, you can replace that literal string with a string constant, but that constant is also not checked, and since it lives in a global namespace with all other identifiers, it needs quite a bit of prefixing to disambiguate:


[[NSNotificationCenter defaultCenter] postNotificationName:WLCoreNotificationModelDidChange object:@"Payload"]
Would it be easy to spot that this was supposed to be WLCoreNotificationModelWasDeleted?

The Macro PROTOCOL_NOTIFY() is removed, whereas the sendProtocolNotification() function is retained for Swift compatibility.

Notification Protocols from Swift

When I introduced Notification Protocols, I mentioned that they should be Usable from Swift.

This is code from a sample Swift Playground that shows how to do this. The Playground needs to have access to MPWFoundation, for example by being inside a Xcode workspace that includes it.


import Foundation
import MPWFoundation

@objc protocol ModelDidChange:MPWNotificationProtocol {
    func modelDidChange( payload:NSNotification );
}

class MyView : NSObject,ModelDidChange {
    override public init() {
        super.init()
        self.installProtocolNotifications()
    }
    func modelDidChange( payload:NSNotification ) {
        print("I was notified, self: \(self) payload: \"\(payload.object!)\"")
    }
}

let target1 = MyView()
let target2 = MyView()

sendProtocolNotification( ModelDidChange.self , "The Payload")

A brief walkthrough:
  1. We declare a ModelDidChange notification protocol.
  2. We indicate that it is a notification protocol by adopting MPWNotificationProtocol.
  3. The notification protocol has the message modelDidChange
  4. We declare that MyView conforms to ModelDidChange. This means we declaratively indicate that we receive ModelDidChange notifications, which will result in MyView instance being sent modelDidChange() messages.
  5. It also means that we have to implement modelDidChange(), which will be checked by the compiler.
  6. We need to call installProtocolNotifications() in order to activate the declared relationships.
  7. We use sendProtocolNotification() with the Protocol object as the argument and a payload.
  8. The fact that we need a protocol object instead of any old String gives us additional checking.
Enjoy!