4

There are huge benefits to pure functions in functional programming, but can the same benefits be obtained in imperative programming with heavy use of the service pattern?

I ask because I want to find a way to map ideas from pure functional programming to imperative programming focusing on using stack space or immortal heap space only. (I.E. A focus on hard real time)

The service pattern I speak of is the same as from here: https://www.schoolofhaskell.com/user/meiersi/the-service-pattern

And by heavy use, I mean having a function only perform effects by the provided effect-full functions passed in its arguments.

Example (in C++):

template <typename SetPixel>
void mandelbrot(float x1, float y1, float stepX, float stepY, int resX, int resY, SetPixel setPixel) {
  float y = y1;
  for (int i = 0; i < resY; ++i, y += stepY) {
    float x = x1;
    for (int j = 0; j < resX; ++j, x += stepX) {
      float za = 0;
      float zb = 0;
      float zm = 0;
      float ca = x;
      float cb = y;
      int k = 0;
      while (zm < 4.0f) {
        float za2 = za * za - zb * zb + ca;
        float zb2 = 2 * za * zb + cb;
        float zm2 = za2 * za2 + zb2 * zb2;
        ++k;
        if (k > 255) {
          k = 0;
          break;
        }
        za = za2;
        zb = zb2;
        zm = zm2;
      }
      setPixel(j, i, k);
    }
  }
}

The above method mandelbrot can be used in both a pure and impure way. I can provide a SetPixel that collects the results and produces an immutable array (making the effects completely local and thus a pure computation). Or I can also pass a effect-full SetPixel and perform the effects directly making it a impure computation.

This allows me to debug functions in a pure fashion or directly perform effects at runtime like so:

  mandelbrot(
    -2.0f,
    -2.0f * 480.0 / 640.0,
    4.0f / 640.0,
    4.0f / 640.0,
    640,
    480,
    [renderer](int x, int y, int c) {
      SDL_SetRenderDrawColor(renderer, (c*5) & 0xFF, 0, 0, 255);
      SDL_RenderDrawPoint(renderer, x, y);
    }
  );

Have I lost any benefits of pure functions by taking this approach?

A second Attempt:

As the comments below and Derek Elkins answer suggests the answer is "No". I have lost the benefits of pure functions.

So here is a 2nd attempt. It uses C++ move semantics + unique_ptr to achieve a linear type system, and then it uses that to implement an effect system in a pure state manipulation style. This is similar to how Mercury does IO.

struct DoNotDelete {
  void operator()(void *ptr) {}
};

struct Void {};

typedef unique_ptr<Void,DoNotDelete> RealWorld;

template <typename SetPixel, typename S>
S mandelbrot(S state0, SetPixel setPixel, float x1, float y1, float stepX, float stepY, int resX, int resY) {
  S state = move(state0);
  float y = y1;
  for (int i = 0; i < resY; ++i, y += stepY) {
    float x = x1;
    for (int j = 0; j < resX; ++j, x += stepX) {
      float za = 0;
      float zb = 0;
      float zm = 0;
      float ca = x;
      float cb = y;
      int k = 0;
      while (zm < 4.0f) {
        float za2 = za * za - zb * zb + ca;
        float zb2 = 2 * za * zb + cb;
        float zm2 = za2 * za2 + zb2 * zb2;
        ++k;
        if (k > 255) {
          k = 0;
          break;
        }
        za = za2;
        zb = zb2;
        zm = zm2;
      }
      state = move(setPixel(move(state), j, i, k));
    }
  }
  return state;
}

template <typename SetPixel>
RealWorld interpreter(RealWorld realWorld, SetPixel setPixel) {
  return move(mandelbrot(
    move(realWorld),
    setPixel,
    -2.0f,
    -2.0f * 480.0 / 640.0,
    4.0f / 640.0,
    4.0f / 640.0,
    640,
    480
  ));
}

Then to kick it off, A RealWorld is constructed somewhere in main(), like so:

  Void realWorldState;
  RealWorld realWorld = unique_ptr<Void,DoNotDelete>(&realWorldState);

  RealWorld realWorld2 = interpreter(
    move(realWorld),
    [renderer](RealWorld realWorld, int x, int y, int c) {
      SDL_SetRenderDrawColor(renderer, (c*5) & 0xFF, 0, 0, 255);
      SDL_RenderDrawPoint(renderer, x, y);
      return realWorld;
    }
  );

This allows me to use a pure immutable value (like an immutable tree map of pixel locations to colours) or the Real World itself.

  • I'm not sure I understand the question. Your mandelbrot template function is a pure function, so how could it lose any benefits of them? – Periata Breatta Nov 28 '16 at 10:53
  • 3
    This is a higher order function without a return value, which can't be useful and pure. – Basilevs Nov 28 '16 at 11:15
  • @Periata Breatta. Pure functions that actually compute something do not tend to return nothing (C++ void or FP unit) they instead return a meaning value, like the result of the computation. When you see a function that does not return a value, then chances are that it is impure and performs some sort of effect. My question is more like does this restructuring keep the benefits? (like referential transparency etc.) – clinux Nov 28 '16 at 11:18
  • @Basilevs. Would continuous passing style be an exception to that rule? – clinux Nov 28 '16 at 11:35
  • 4
    Referential Transparency means that you can replace any expression by the result value of evaluating that expression without changing the meaning of the program. Since mandelbrot doesn't return anything, this means that you should be able to simply delete it, without changing the meaning of your program. If that is indeed possible, then yes, you haven't lost referential transparency. Otherwise, you have lost it. – Jörg W Mittag Nov 28 '16 at 11:38
2

As the referenced article mentions, this is very close to mimicking some basic OOP in Haskell, though, as it mentions, it provides first-class composition. It's also closely related to dependency injection as is commonly practiced in OOP. Either way, one way to think about and model what's happening is via the concept of object-capabilities.

In an object-capability language, the authority to do something is captured by the notion of a capability. Usually these are specific I/O related things, but it can be more abstract. The key idea is that the only way you can get a capability is if someone gives it to you. To make a language that enforces that property, you need two things: encapsulation like you're used to in most OO languages, and the removal of all ambient authority. Roughly speaking, this means for a language like Java, with no "top-level" classes/functions that have authority and no global mutable variables, e.g. mutable static (in the Java/C# sense) properties of a class. Most OO languages provide the necessary encapsulation (though not C++), but few eliminate ambient authority. Removing it forces a dependency-injection-like style. This is pretty clearly illustrated in the language Newspeak.

The benefits you mention are common benefits of object-capability languages and dependency injection. In fact, in object-capability languages, the ability to wrap or mock any authority carrying object is the basis of sandboxing and revocable capabilities. That said, all this was a bit of a non-sequitur with regards to your question.

The answer to your question is basically "no". The benefits you mention are not benefits of purely functional code but benefits of making your dependencies explicit. The benefits of purely functional programming with respect to imperative programming accrue because imperative reasoning is hard. At the end of the day, to reason about the correctness of code using mandlebrot despite it being "pure" (sort of) would still require imperative reasoning. (Obviously, since the implementation of mandelbrot is imperative, you are still forced to use imperative reasoning to verify its correctness.)

If you took an approach more like, e.g., Haskell's IO monad, which would address the comments about "not returning anything", and returned some (general) representation of what to do, you would still largely or entirely be required to employ imperative reasoning techniques to verify that your program is correct. This is why programming in the IO monad in Haskell is not much easier than doing imperative programming in a typical language. On the other hand, if you returned a simpler, more specialized representation of what should be done, a commonly used technique in Haskell, then you could much more strongly leverage reasoning techniques that only apply to purely functional code. For example, you could return an array of pixels to update. This technique ends up producing some of the same benefits of the object-capability/dependency-injection approach by pushing all the authority-requiring work to an "interpreter" function. Implementing that interpreter function, though, can still greatly benefit from object-capability techniques.

In general, I strongly recommend pretending (if it's not actually the case) that various authorities are accessible only through capabilities. To the extent that the assumption that you're working in an object-capability system holds, you do gain significant simplifications while having flexible code.

  • You are absolutely correct, "imperative reasoning" was still happening. I've made a 2nd attempt in the Question above. Does it do any better? – clinux Nov 29 '16 at 9:37
  • 1
    @clinux Not really. As I said, even in Haskell using the IO monad isn't really any easier than imperative programming. Your transformation only makes it more explicit why it's difficult. Conceptually, RealWorld represents the whole state of your program (and then some...), so setPixel can modify any piece of state in the program. Arguably, mandelbrot's specification should allow setPixel to modify anything it wants as long as it updates the pixels appropriately. If it does, then the exact sequence of setPixel calls matters, or it's specification is highly non-deterministic. – Derek Elkins Nov 30 '16 at 6:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.