A little stack machine

Threw this together to show an example of computed goto. Computed goto is a handy tool for building little interpreters.


#define NEXT goto **ip++
int main()
  int fact = 6, fact_b0 = 16;
  void* program[] = { 
    &&push, (void*)5, &&call, (void*)fact, &&printi, &&end,
    &&beq0, (void*)fact_b0, &&dup, &&push, (void*)1, &&sub, &&call, (void*)fact, &&mult, &&ret, 
    &&pop, &&push, (void*)1, &&ret  };
  void** ip = program;
  void* stack[16] = {0}; void** sp = stack-1;
  void* cstack[16] = {0}; void** cp = cstack-1;
  *++cp = ip+1; ip = program + (int)*ip;
  ip = *cp--;
  ip = *sp ? ip+1 : program + (int)*ip;
  *++sp = *ip++;
  sp[1] = sp[0]; sp++;
  sp[-1] = (void*)((int)sp[-1] * (int)sp[0]); sp--;
  sp[-1] = (void*)((int)sp[-1] - (int)sp[0]); sp--;
  printf("%i\n", (int)*sp--);
  return 0;

On codepad

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);
        return mbind(f(i, *begin), [=](T result){
            Iter next = begin;
            return foldM(next, end, result, f);

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

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”

Comma Abuse

Found this old C++ source file in my scratch directory, apparently from last September. I don’t even remember writing this, but it’s written using my idioms. If I did write it, rest assured it was primarily for amusement purposes (abusement purposes?) only.

#include <iostream>
using namespace std;

int fibonacci(int x) {
    int a=0, b=1, temp;
    return a;

int main() {
    int i = 0;

Yeah. That was terrible. Terrible awesome. But looking back, I’m realizing that some of the comma abuse is superfluous:

int fibonacci(int x){
    int a=0, b=1;
    return a;

Don’t let anyone check in code like this, ever.

Native Client at UWCS lecture

Available for streaming and download, Google Native Client presented at UW’s computer science lecture series. Covers the restrictions on x86 code, new alignment rules, and performance on various benchmarks. 5% overhead, that’s nothing compared to many other sandboxing techniques.

Native client is 50KB download?  Wild. It really is just a gatekeeper, runtime library separate.

Of course, I would love to get away from x86.  LLVM, or ARM, or even Amd64.  x86 makes me a sad panda.

Return-code vs. Exception handling

(Originally authored Feb 2008.  This is a revision of an older post from before I began blogging on the internet at large.  It’s been edited for style, not content)

This is one of those “religous wars” in programming language theory; return code handling (RCH) vs exception handling (EH).  Firstly, I am biased.  Secondly, I will try to remain objective as well, partitioning observations of code using these mechanism from how I feel this reflects on the utility of either mechanism.  I tend to _prefer_ EH in general, but not universally, and generally follow the viewpoint that “exceptions are for exceptional things”.  With that aside…

Raymond Chen wrote an article a while back on RCH vs EH[2]. There, he points out accurately some facts about code review of RCH and EH, concluding that it’s generally harder to conclude the failure-safety of some example the RCH code than some comparable EH code.

He’s right.  And he’s wrong.  His article is incomplete.  Lets start with defining the playing field.

Continue reading “Return-code vs. Exception handling”

Memoizer, in C++

Part of what I’m trying to do here is record experiments, little bits of code demonstrating software techniques.  This is a revisit of a recent one.

As a refresher, memoization is a dynamic programming technique used to optimize the time to solve problems where partial problems overlap frequently.  For example, in the recursive definition of the Fibonacci sequence, F(x) = { 1 : x < 2,  F(x-1)+F(x-2) : x>=2 }, at each stage, you compute the solution by taking the results from two separate computations.

So, walking briefly through, get the C++ bootstrapping out of the way.  To start, we include the standard module’s we’ll be using:

#include <iostream>
#include <iomanip>
#include <map>

Next up, the memoizer — this is a helper class that will record the results for us. 

template <
    class Result, 
    class Arg,
    class ResultStore = std::map<Arg, Result>
class memoizer1{
    // accelerate 'f' by remembering partial results
    template <class F>
    const Result& operator()(F f, const Arg& a){
        typename ResultStore::const_iterator it = memo_.find(a);
        if(it == memo_.end()) {
            it = memo_.insert(make_pair(a, f(a))).first;
        return it->second;
    ResultStore memo_;

We’ll separate the definition of fibonacci function from the public surface so that the memoizer can be applied later

int fib(int);

namespace {
    // instrumentation, track number of uses
    int total_ops = 0;

    // implementation
    int fib_(int n){
        if(n == 0 || n == 1) 
            return 1;
            return fib(n-1) + fib(n-2);

Lastly the driver function will decorate the implementation with a memoizer, and a prompt loop.  You should be able to copy-paste the code into a cpp file, comple, then run.

// driver function
int fib(int n) {
    static memoizer1<int,int> memo;
    return memo(fib_, n);

using namespace std;

int main(){
    cout << "fibonacci numbers, memoized, ctrl+z to quitn";
    for(;;) {
        cout << "enter integer: ";
        int x;
        if(!(cin >> x))

        total_ops = 0;
        int y = fib(x);

        cout << "fib(" << x << ") == " << y << endl;
        cout << "cost was " << total_ops << endl;

And that’s the complete program.  Trying it with a few inputs, you’ll see few number of operations.  To see the non-memoized results, you need only comment out the code for ‘fib()’ and have it invoke ‘fib_’ directly — the results will slow to a halt around x=30 to 35.

By using a look up table, each time ‘fib’ is invoked with a given value of ‘x’, the result is stored so it doesn’t need to recurse again.  A hash table, or even a dynamically sizing array (std::vector) could have also been used in this case, but may not be appropriate for other problem spaces.