λ Tony’s blog λ

I have 2 children, (almost) 6 and 4 years old, who have recently come under attack by the pawns of an elitist minority-led Christian organisation that is supported by our government and other elitist organisations. The sad part is that these so-called ‘pawns’ are unaware that indeed they are acting as pawns. The internalisation of the legitimacy of their ignorant stance has surpassed the point of conscious denial and is so prolific, that I very much doubt that this realisation will ever come to fruition. Despite this sad state of affairs, I must maintain the well-being of my children — at all costs — and this may require the absolute refusal to permit even the most remote hint of indoctrination of the purported filth to my children who are in no position to defend themselves against it. The persistence of the manipulators, and most importantly, those being manipulated, often requires quite a fervent and directed response from me — the protector of my children.

I am writing this post to address these people who are conducting these attacks, even though I know that it is probably futile, given their own lack of recognition of their actions. You may accuse me of “not giving my children a chance to make up their own mind” or blatantly disallowing established beliefs, despite their widespread proliferation. I accept these allegations, thank you for your (no doubt conscious) concern, but reject the legitimacy of the accusations, without further explanation. Unlike the religious establishment, free thinkers have absolutely no problem whatsoever shifting position in light of compelling evidence. My children are, and will be, free thinkers and your actions are detrimental to this objective. I withdraw any attempts to justify my position, not because I am arrogant or have some kind of personal conviction with my stance — simply, I do not wish to engage in your war. Call me Switzerland, call me a coward, call me whatever, heck, cast me to a furnace for eternity, but please don’t do it in front of my children. Please (oh please) understand.

Nevertheless, to express my dissent and fear for the well-being of my children is not the primary objective of this post. Instead, it is to express a common misnomer. Often times, I am accused of undermining the value of those who conduct blatant attacks with their irrational beliefs as human beings. Please be assured, I do not think less of you than another, even myself. You are an equal.

Some people don’t like pain — when they watch someone else smack their head on a tree, they cringe with empathy. In fact, if the poor victim could be warned of the impending danger somehow, I am sure that an empathetic person would make every effort to make it the case to prevent the infliction of pain. This is exactly my response to those who have been robbed of the ability to think critically. I have absolute, paramount sympathy for your position, well beyond that of any other position that I could possibly imagine — even extreme pain (I have had stitches in 23 separate sites on my body, including one amputation and one ’sewing it back on’ — I have felt pain).

Please also be assured that my response to the attack of my children must take priority over the expression of this sympathy. My response may appear to be in complete contradiction to what I have just declared — but it is not the case universally. I must put aside my own self-indulgences in expressing sympathy when protecting my children — they are just so vulnerable and trusting.

Please, please understand, just for a brief moment even.

“None are more hopelessly enslaved than those who falsely believe they are free” -Johann Wolfgang von Goethe
…and they receive my sincere condolences for the loss of control of their own mind.

Coming from an imperative language such as Java/C/C# and moving to a functional language, you will almost certainly encounter ‘folding functions’. There are usually two folding functions (sometimes there are minor variants) — one folds to the right and the other folds to the left. In Haskell, these functions are named foldr and foldl.

This first encounter with folding functions can often be quite daunting, but I propose an alternative approach. In fact, these folding functions are almost certainly quite familiar to the imperative programmer — just without consciousness. If I had a dollar for every time I saw something like this (I’d buy every CS student a book on the lambda calculus :)):

  ...
  B accum = b;
  for(final A a : as) {
    accum = f.f(a, accum);
  }
  return accum;

Look familiar? Not so daunting? Great, because it’s a fold — specificially, a fold to the left. It is a fold to the left because the sequence (list, array, whatever) is iterated from the left/start to the right/end. Conversely, a fold right iterates from the right/end of the sequence to the left/start.

Let’s take a closer look at the ‘fold left’ above. The first line initialises an accumulator of type B to the given argument. Then the sequence (of A) is iterated and each element is passed to some function and its result assigned to the accumulator. Finally, the accumulated value is returned.

Have I just trivialised a seemingly complicated concept? Not at all! I have undermined its apparent complexity perhaps. On the contrary, it is the imperative language version that has complicated a trivial concept. Let’s take a look at a complete and compilable example:

class Foldr {
  static interface F<A, B> {
    B f(A a, B b);
  }

  static <A, B> B foldr(final F<A, B> f, final B b, final A[] as) {
    B accum = b;

    for(int i = as.length - 1; i >= 0; i--) {
      accum = f.f(as[i], accum);
    }

    return accum;
  }
}

class Foldl {
  static interface F<A, B> {
    A f(A a, B b);
  }

  static <A, B> A foldl(final F<A, B> f, final A a, final B[] bs) {
    A accum = a;

    for(final B b : bs) {
      accum = f.f(accum, b);
    }

    return accum;
  }
}

public class Folds {
  public static void main(final String[] args) {
    final Integer[] i = new Integer[]{7,8,9,42,11,13,45,54,45,46,64,74};

    final Integer right = Foldr.foldr(new Foldr.F<Integer, Integer>() {
      public Integer f(final Integer a, final Integer b) {
        return a - b;
      }
    }, 79, i);

    System.out.println(right);

    final Integer left = Foldl.foldl(new Foldl.F<Integer, Integer>() {
      public Integer f(final Integer a, final Integer b) {
        return a - b;
      }
    }, 97, i);

    System.out.println(left);
  }
}

Phew! What an effort — pass me a beer!

We notice in the main method that the types of both A and B are the same (Integer). This is purely consequential and these types may, and often do, differ. Also notice that our function in each case is not commutative. That is, f(a, b) is not necessarily equivalent to f(b, a). We know this because a - b is not necessarily equivalent to b - a. If the functions were commutative, then the result of a fold right would be equivalent to the result of a fold left. If you execute the code above, you will not get the same output for each fold. Try changing the implementation of each function to be commutative (like +) and observe the equivalent results.

Let’s take a look at the Haskell equivalent at an interpreter:

Prelude> let i = [7,8,9,42,11,13,45,54,45,46,64,74]
Prelude> foldr (-) 97 i
41
Prelude> foldl (-) 79 i
-321

Same outputs as the imperative code? Good, so that’s folds out of the way — easy peasey
By the way, yes the Haskell equivalent is supposed to be 100 times shorter — that is the nature of a relatively expressive programming language.

I have been reading articles lately that make a case for or against ’strong type systems’ by referring to artifacts that purport the exact opposite of a strong type system such as Java, C/C++, C# or a few other weak type systems. This is unfortunate, since the remainder of the article becomes immediately invalid within the first two or three sentences and I doubt that the author is even aware of the fact that they are wasting their own time while at the same time, misleading any potential readers. Quite often, these articles have trendy or appealing writing styles, such as “Parabola“, which attempts to universally refute the legitimacy of type safe (T.S. in the article) systems by making a rather clever, albeit erroneous, metaphor with a scenario in an airport.

There are countless articles that talk about the problems with null, but is this a problem with type systems? No, it is a very poor solution to work around one of the fundamental contradictions that plagues imperative programming. That is, even if we must keep this contradiction and imperative programming for some reason (which we don’t), there are better solutions than null. So this leaves a problem for any author who wishes to provide a higher understanding for their readers; do they explain all the problems with null in more formal, concise and correct terms knowing that the whole problem disappears with a better foundational grounding (eliminating imperative programming), or do they simply present some alternatives that may be unfamiliar and hope for initiative on the part of the reader who will use (the ever so common) gut instinct to feel that they have a superior solution? A horrible problem that is thankfully not mine.

Just what denotes Java et. al. having a weak type system? On what basis is this statement made? The answer to this question is not trivial by any means and answering it requires a reasonable amount of foundational mathematics knowledge, which leads to specialisation in type theory — both of which not many software developers have, nor have the initiative to acquire (this is sad :(). In any case, a brief attempt can be made. There is no doubting that these weak type systems disallow a certain amount of expressivity and force a rigid and sometimes unreasonable method of development. That is not to say that dynamic typing is the solution. Just like Dawkins said that since the beginning of life is so improbable as to be impossible (on the surface), then the existence of a supernatural creator is not the only alternative solution — referring to Darwinism. Whether or not you believe in a supernatural creator, it would be obscene and somewhat ignorant to immediately jump to such a conclusion without rational reason — such as critically analysing alternatives. Likewise, it is obscene to jump to the conclusion that dynamic typing solves the problems of (weak) existing type systems without considering alternatives, such as expressive type systems.

Using Java et. al., it is impossible to express certain fundamental programming concepts and many more concepts that are specific to the problem at hand. One such fundamental programming concept is the monadic bind computation. Before I start going into detail about this, I am compelled to first dispel a very common myth. Many ‘programmers’ believe that monads (and therefore, monadic bind) are not relevant to their problem, since their language does not support such a concept directly. Few programmers actually realise that they are in fact using monads, just without language support and often in a somewhat contrived manner — a result of the lack of formality in reasoning. In fact, I postulate that in my time working on IBM WebSphere 6 and the IBM JDK 1.5, I saw somewhere in the order of hundreds of monads littered throughout thousands of lines of code. Furthermore, Java/C# has one particular monad built right into the language. Providing concrete examples is worthy of a topic on its own, so I will instead take the liberty of claiming that if anyone were to send me their 2^gazillion LOC application, I would be capable of finding one monad per one thousand LOC — worst case scenario. At least, please assume so for now. Yes, monads are extremely important and common to programming, even if you don’t ever know it explicitly. Great, glad that is out of the way
We cannot express monadic bind with these weak type systems because they do not have higher-order types. What is a higher-order type? A few people with much more time, specialisation and knowledge have done a better job than I am at least willing and probably capable, of doing. Instead, I will attempt to demonstrate what happens when you attempt to generalise monadic bind with a weak type system. Haskell is a purely functional language that does have higher-order types. If we ask a Haskell interpreter for the type of bind (>>=), we get the following:

Prelude> :type (>>=)
(>>=) :: (Monad m) => m a -> (a -> m b) -> m b

This is akin to a Java/C# interface (called Monad) containing one function (>>=) or ‘bind’, however, we will note that there is no analogy for this expression in a weak type system. This fact, along with many others, seems to be quite a hurdle in grasping the very concept of the bind computation itself. If we examine this type expression, we could say that the bind function (>>=) takes two arguments:

1. a monad with a type parameter ‘a’
2. a function from ‘a’ to a monad with a type parameter ‘b’

The function returns a monad with a type parameter ‘b’. ‘Implementing this interface’ would make the class itself an instance of Monad and so itself can be used as the function arguments. This is one of many things that higher-order types gives us.

Let’s attempt this with a weak type system, Java. First, we acknowledge that Java has no first-class functions (cannot pass functions as arguments), but we can loosely emulate it (good enough for our purposes) with a single interface:

interface F<X, Y> {
  Y f(X x);
}

Let’s attempt to write the Monad interface:

interface Monad<A> {
  <B> Monad<B> bind(Monad<A> ma, F<A, Monad<B>> f);
}

Looking good so far. But don’t be fooled — there is a huge problem. Namely, that the interface cannot be implemented correctly. Keeping with tradition, let’s attempt to write the Maybe monad:

final class Maybe<A> implements Monad<A> {
  // BZZT! WRONG!
  Maybe<A> bind(final Maybe<A> ma, final F<A, Maybe<B>> f) {

We hit our first problem, can we work around it? In Java, we have co-variant return types, but we do not have higher-order types. This means that we can keep our return type declaration, but not the types of our arguments — they must match the interface. Then, we can resort to casting — an abomination that indicates a flaw of the type system.

Let’s try again:

final class Maybe<A> implements Monad<A> {
  public <B> Maybe<B> bind(final Monad<A> ma, final F<A, Monad<B>> f) {
    if(ma instanceof Maybe) {
    ...

This solution works, but we have to admit to having to work around the type system by resorting to casting. As a result, I will no longer call it a solution, but instead, it is a work around — a flaw in the expressitivity of the type system. The lack of higher-order types in common type systems is one of many problems with quite devastating consequences. In attempting to model a fundamental computational concept, we find that the type system of Java (and many other programming languages with weak type systems) is not a sound premise from which to extrapolate conclusions about type systems in general. If we were to do so, we would be making a fundamental mistake. In fact, this particular problem is one that dynamic typing appears to solve. But don’t let these superficial appearances delude you. A stronger type system is the correct solution.

Here are some conclusions from these findings:

• Higher-order types are fundamental to a strong type system
• Java/C/C++/C# et. al. do not support higher-order types, therefore, do not have a strong type system
• Monadic bind is a relatively trivial, yet extremely common programming concept
• Monadic bind cannot be easily expressed in common weak type systems
• Dynamic typing is not the only apparent solution to resolving the problems of weak type systems

Here are some questions to ponder:

• What if we tried to model a concept that is not as trivial as the bind computation? Does the difficulty of expression grow linearly to the complexity of the concept?
• What other concepts are supported by strong type systems but not our common weak type systems?
• Can we come up with other examples of common, trivial concepts that cannot be expressed because these weak type systems are missing some other feature besides higher-order types?
• Most importantly, what does a comparison between a type system that exemplifies sound, strong and expressive type safety with dynamic typing (or no typing) give us?

It is this latter question that needs to be explored before drawing any potentially misleading conclusions about type systems. It is a crucial mistake to make a comparison to weak type systems that do not in any way exemplify soundness, as anything else but unsound examples of type systems. The implication that dynamic typing is a correct solution is a blind-man’s fallacy.

A compilable solution follows:

interface F<X, Y> {
  Y f(X x);
}

interface Monad<A> {
  <B> Monad<B> bind(Monad<A> ma, F<A, Monad<B>> f);
}

final class Maybe<A> implements Monad<A> {
  public <B> Maybe<B> bind(final Monad<A> ma, final F<A, Monad<B>> f) {
    if(ma instanceof Maybe) {
      final A j = ((Maybe<A>)ma).just();
      if (j == null) {
        return new Maybe<B>();
      } else {
        final Monad<B> b = f.f(j);

        if(b instanceof Maybe) {
          return (Maybe<B>)b;
        } else {
          throw new Error("Just because we don't have higher-order types," +
            "doesn't mean we start doing silly stuff");
        }
      }
    } else {
      throw new Error("I said stop doing silly stuff! Please!");
    }
  }

  // Let's just hack for now.
  // null denotes 'Nothing'.
  // Many programmers will be familiar
  // with this idiom (did I say hack?)
  // anyway.
  //
  // A more complete solution is provided at
  // http://blog.tmorris.net/revisiting-maybe-in-java
  private final A a;

  public Maybe() {
    this.a = null;
  }

  public Maybe(final A a) {
    this.a = a;
  }

  public A just() {
    return a;
  }
}