Categories for Programmers: The Yoneda Lemma

Good idea; can you explain it in terms of software engineering? What software engineering problem is it solved by this lemma?

E.g. Starting with this set of requirements, we are transported to a solution thusly: ...

So it's the same thing as always: make a stable API and code against it.

The commutative diagrams, rather, remind me of diagrams that I remember from chemistry. We can go from this molecule to that one via this path or that one, and the energy deltas are the same.

Speaking of continuations, I'm currently looking at porting the trick used by some OCaml people of doing delimited continuations on the C stack, into my own language. It's pretty neat: just copy the C stack into a closure-like object, and then when you need to invoke the continuation, swap that segment back onto the regular linear stack (into a stable space prepared using alloca). Rebuild some exception handling chains through this new pieces of stack, and then invoke the thing using an exception (ultimately a longjmp). When it is done running, you can blow it away. All permanent effects are in external environments that are on the heap. The next time you call into it, you just copy it in the same way.

I'm unclear on how you can do a longjmp to something that has been copied elsewhere on the stack relative to its original location. I mean, the jmp_buf probably has an absolute stack pointer in it which it restores. I have to look at their code again; the obvious hack is to scan the jmp_buf for values that look like pointers into the stack area and adjust those values.

I implemented a stack copying hack once to get a 64 bit Linux kernel on MIPS to call into 32 bit firmware, passing ordinary local variables (whose addresses are 64 bit values on a 64 bit stack) to the firmware functions. I copied the kernel thread's stack into a buffer 32 bit addressable space. Then I adjusted all internal pointers within that stack to point to the correct places in the new location. The threads's pointer was then thunked into that space around the call to the firmware. The firmware API wrapper was then seeing data addresses whose lowest 32 bits could be passed down to the firmware routines via 32 bit registers and still point to the correct data. Of course, a reverse copy from the faked stack was then done to retrieve any results which the firmware routine wrote into local buffers. This worked well enough that I was able to expose boot firmware environment variables through a /proc interface (even making it writable!) Based on such past experience, I'm confident I can do this delimited continuation hack.

No problem:

  struct symbol {
    obj_base_fields; // macro
    obj name_string;
    obj package;
    // ...
  };

  struct cons {
    obj_base_fields; // macro
    obj car, cdr;
  };

I think about something like Stokes' theorem: The integral of a function over the boundary of a manifold is equal to the integral of the derivative of the function over the interior of the manifold. But in practice, one integral or the other is often easier to do; that means that the theorem has the practical effect of letting you transform some hard problems into equivalent but easier problems.

But note well that I said "some problems". There are many problems that this won't help with. There are others where the problem you're trying to solve is the easier one, and applying the theorem turns it into a harder problem.

I suspect (but do not know) that the Yoneda Lemma is similar. It can sometimes give you a simpler way of looking at a problem. But just sometimes. Sometimes the Haskell/ML view is the easiest way to solve the problem you have. And sometimes it's not.