Rubrication

In my last post I described how unbelievably cool modules are in Coq. Well it turns out that there is some disagreement in the community about whether one should even use them!

Why? Because the type system in Coq is so powerful we hardly even need them. In fact with a bit of syntactic sugar for inductively defined types and the generation of constructors we magically get something like first class modules (first-class meaning modules that are actually values that can be passed around to functions etc…). Enter the Record.

Record MonadBind : Type :=
  { M : forall (A : Type), Type;
    bind : forall (A B : Type), M A -> (A -> M B) -> M B;
    ret : forall (A : Type), A -> M A;
    left_unit : forall (A B : Type) (f : A -> M B) (a : A),
      bind A B (ret A a) f = f a;
    right_unit : forall (A B : Type) (m : M A),
      bind A A m (ret A) = m;
    bind_assoc : forall (A B C : Type) (m : M A) (f : A -> M B) (g : B -> M C) (x : B),
      bind B C (bind A B m f) g = bind A C m (fun x => bind B C (f x) g)
  }.

This implements exactly the same strict controls on the instantiation of a Monad that were given with our MONAD signature in the previous post. Each type can rely on previously defined types in the record giving us the full dependent type system needed to specify a proper monad. With a little bit of work we can rewrite our module to be an instantiation of a record.

Look here for the example code

How cool is that!

Recently on Lambda the Ultimate there was a post called “Total Functional Programming”. The title didn’t catch my eye particularly, but I tend to read the abstract of any paper that is posted there that doesn’t sound terribly boring. I’ve found that this is a fairly good strategy since I tend to get very few false positives this way and I’m too busy for false negatives.

The paper touches directly and indirectly on subjects I’ve posted about here before. The idea is basically to eschew the current dogma that programming languages should be Turing-complete, and run with the alternative to the end of supplying
“Total Functional Programming”.

At first glance this might seem to be a paper aimed at “hair-shirt” wearing functional programming weenies. My reading was somewhat different.

Most hobbiest mathematicians have some passing familiarity with “Turing’s Halting Problem” and the related “Goedel’s Incompleteness Theorem”. What this paper is trying to do is say “So what!”. The basic idea is that restriction to a syntacticly restricted language can restrict the semantics in such a way that these problems do not apply. The resulting (*huge*) class of programs can then solve almost everything that we think is important.

The “Bazooka” of the paper is a line describing how every program for which we have a complexity upper bound, is in fact inside the restricted language. This realisation is profound. It means that all of the algorithms that anyone has bothered to find upper bounds for (a huge class of programs mind you!) is accessible to this technique.

The paper even deals with infinite data (co-data) in the framework and mechanisms to properly account for streams and other (possibly) infinite structures.

The idea of working in syntactically restricted languages that are sub-Turing (for any number of reasons) is not new. In fact I think I’ve mentioned DataLog (wikipedia entry) previously. In the case of DataLog however, there are serious deficiencies in the expressive power.

Definitely the best paper I’ve read this year. I’m not sure how accessible it is to lay-people, but it should be accessible to anyone with a CS B.S. or people who have some familiarity with functional programming.