Concepts: Typeclasses for C++?

I’ve had a hypothesis for a while that C++ templates (paired at times with ADL) are an ad-hoc, unsound version of typeclasses. I’ve seen this hold for parser combinators, range base algorithms, and more. I’m also not the first to draw this comparison[1].

Concepts are supposed to bring soundness in through constrained templates. Concepts look awfully a lot like type classes; they export functions and types, and are parameterized, and act as constraints on generic functions and other concepts. I checked the draft specification [2], and it even seems to permit parameterizing concepts on type constructors, just like Haskell! (er, C++ calls them class templates, not type constructors. to-may-to, to-mah-to)

But I worried I may be mistaken about concepts, as I’ve searched through google and literature and have yet to find a single example in literature demonstrating the use of template template concepts.

In case you’re curious what this might look like, here’s an educated guess:

concept Monad<template <> class m> {
  template<typename T, typename U>
  m<U> mbind(m<T>, function<m<U>(T)>);

  template<class T>
  m<T> mreturn(T);
};

template <template <typename> class m,
          class T,
          class U,
          class Iter>
requires M<m>
requires InputIterator<Iter, U>
m<T> foldM(Iter begin, Iter end, T i, function<m<T>(T, U)> f)
{
    if(begin == end)
        return mreturn(i);
    else
        return mbind(f(i, *begin), [=](T result){
            Iter next = begin;
            ++next;
            return foldM(next, end, result, f);
        });
}

Have template template concepts been covered thoroughly somewhere, and I’ve just missed it?

Repls, repls, everywhere

Have a new-years resolution to try out a new programming language, but in too much of a hurry to pick only one, or install anything?

Online REPs and REPLs

Today there’s 61 different languages on that list. That many, there’s gotta be at least one that strikes your fancy.

Best batch execution site: ideone.com with 50 unique languages.

Best interactive REPL site: repl.it with 16 unique languages.

Only a Mathematician would say

I came across a version of Dijkstra’s “Goto Considered Harmful” annotated by David Tribble. A lot has changed since then; the annotated version is perfect for acquiring the right context to read the paper.

There was a particular line by the annotator that continues to amuse me:

Dijkstra seems to imply that iterative looping (inductive) statements are intellectually harder to grasp than recursion, which is the kind of thing only a mathematician would say.

Among the ways you can bisect computer science, is whether this statement insults or compliments.

Bondage and Discipline Python

Python has an identity crisis sometimes. It starts with the premise, from Guido’s prior work on ABC, to make a simple but easy to understand language.

But then turns around and cries out “one way to do it“, leaving the programmer perplexed as to how Guido van Rossum thought we should do things. For example, Guido hates tail calls, so recursion isn’t the one way to do it that he picked (note that his blog post and followups contain a large number of factual errors; read it as an opinion piece only).

During these fits, Python suffers itself to be a bondage and discipline language.

Apparently there is hope. One bit that causes me particular pain is that nested functions cannot rebind variables in the outer scope; only read from them. A case in point:

def f():
  x = 1
  def doubleIt():
    x *= 2 # local variable 'x' referenced before assignment
  doubleIt(); doubleIt();
  return x;

However, I was reading a piece on Factor, and it mentions that this restriction is lifted in Python 3.0. I’m still on 2.6 (the only differences I had been aware of were the somewhat arbitrary swapping of the ‘/’ and ” operators, and the insulting removal of map, filter, and reduce from Python 3.0). However, fixing this scoping rule, even if an extra keyword is needed, sure would be convenient for me.

Actually, there are a lot of improvements:

  • Various APIs returns views instead of mutable list (copies).
  • sorted is now built in. (I’ve had to write that myself so many times…)
  • Apparently map and filter are still here (though he still went and put reduce all the way off in functools. I guess you can’t have it all -_-)
  • Set literals, yay!

Now, if Guido would be so kind to add proper statement support to lambdas, I’ll switch ^_^. Oh, but Guido hates lambdas. Oh well, next time maybe.

— signed an ambivalent Python user

The case of the different shifts

Larry Osterman has commented on an interesting edge case in the C/C++ standards, involving the underflow of the right shift operator.

They reported that if they compiled code which calculated: 1130149156 >> -05701653 it generated different results on 32bit and 64bit operating systems. On 32bit machines it reported 0 but on 64bit machines, it reported 0x21a.

This is one of various areas of “undefined behavior” for which you can ask 2 engineers what it should do and get 3 answers, at least one being that “but I know there must be one!” I think I know where at least 2 of the answers are coming from … Continue reading “The case of the different shifts”

Eval in Python

I’ll just leave this here for you:

Wait what. Python compiles? That is correct. CPython and PyPy (the implementations worth caring about currently) are in fact creating a code object from the string you pass to exec or eval before executing it. And that’s just one of the things many people don’t know about the exec statement.

It doesn’t always have to be about theory, nor should it be. I might recommend this article for programmers already versed in Python, to read side by side or leading up to SICP’s “Metalinguistic Abstractions” chapter.

Kindle programming (part 1)

I bought an Amazon Kindle 3G back in October. So far I’ve mostly been reading research papers on it (that 3rd gen eInk really is amazing), occasionally proggit.

I applied for SDK access, but heard nothing back. So instead, I’m using the built in “experimental” web browser. It has canvas support, so I’m golden.

Image of Kindle web browser displaying vector fonts.

As you might have noticed, I couldn’t resist the urge to design a vector font for the task; please be gentle, I know the font leaves a lot to be desired, it’s a work in progress. The Kindle browser didn’t seem to have font support anyway, while public domain, I didn’t particularly enjoy the Hershey fonts. The Hershey fonts are nice, but they’re unsuitable for programming.

Quickrefs for Python and Vim

More quick reference booklets:

I don’t really need the qr for Python, but I thought it might be good to have ready should a friend a coworker wish to start learning Python.

As for Vim, the reference is certainly terrible – I’ve barely used it at all. The qr is just a list of commands that looked useful. I’ll edit the qr as I go, perhaps using the last pages for notes.