I learned to program...

I've been struggling with a blog post that may never see the light of day. In the mean time, have you seen this?

index of blog posts

Lisp interpreter in 90 lines of C++

I've enjoyed reading Peter Norvig's recent articles on Lisp. He implements a Scheme interpreter in 90 lines of Python in the first, and develops it further in the second.

Just for fun I wondered if I could write one in C++. My goals would be

1. A Lisp interpreter that would complete Peter's Lis.py test cases correctly...
2. ...in no more than 90 lines of C++.

Although I've been thinking about this for a few weeks, as I write this I have not written a line of the code. I'm pretty sure I will achieve 1, and 2 will be... a piece of cake!

In one short line of Python Mr. Norvig implements Lisp functions car, cdr and append. Another line and we've done the four basic mathematical operators on bignums. Gulp.

To give myself any sort of chance I don't intend to support bignums, garbage collection or error handling and I'm only going to implement the bare minimum to pass the test cases.

. . .

OK, I've done it. Here it is:

// Scheme Interpreter in 90 lines of C++ (not counting lines after the first 90). // Inspired by Peter Norvig's Lis.py. // Made by Anthony C. Hay in 2010. See http://howtowriteaprogram.blogspot.co.uk/ // This is free and unencumbered public domain software, see http://unlicense.org/ // This code is known to have faults. E.g. it leaks memory. Use at your own risk. #include <iostream> #include <sstream> #include <string> #include <vector> #include <list> #include <map> // return given mumber as a string std::string str(long n) { std::ostringstream os; os << n; return os.str(); } // return true iff given character is '0'..'9' bool isdig(char c) { return isdigit(static_cast<unsigned char>(c)) != 0; } ////////////////////// cell enum cell_type { Symbol, Number, List, Proc, Lambda }; struct environment; // forward declaration; cell and environment reference each other // a variant that can hold any kind of lisp value struct cell { typedef cell (*proc_type)(const std::vector<cell> &); typedef std::vector<cell>::const_iterator iter; typedef std::map<std::string, cell> map; cell_type type; std::string val; std::vector<cell> list; proc_type proc; environment * env; cell(cell_type type = Symbol) : type(type), env(0) {} cell(cell_type type, const std::string & val) : type(type), val(val), env(0) {} cell(proc_type proc) : type(Proc), proc(proc), env(0) {} }; typedef std::vector<cell> cells; typedef cells::const_iterator cellit; const cell false_sym(Symbol, "#f"); const cell true_sym(Symbol, "#t"); // anything that isn't false_sym is true const cell nil(Symbol, "nil"); ////////////////////// environment // a dictionary that (a) associates symbols with cells, and // (b) can chain to an "outer" dictionary struct environment { environment(environment * outer = 0) : outer_(outer) {} environment(const cells & parms, const cells & args, environment * outer) : outer_(outer) { cellit a = args.begin(); for (cellit p = parms.begin(); p != parms.end(); ++p) env_[p->val] = *a++; } // map a variable name onto a cell typedef std::map<std::string, cell> map; // return a reference to the innermost environment where 'var' appears map & find(const std::string & var) { if (env_.find(var) != env_.end()) return env_; // the symbol exists in this environment if (outer_) return outer_->find(var); // attempt to find the symbol in some "outer" env std::cout << "unbound symbol '" << var << "'\n"; exit(1); } // return a reference to the cell associated with the given symbol 'var' cell & operator[] (const std::string & var) { return env_[var]; } private: map env_; // inner symbol->cell mapping environment * outer_; // next adjacent outer env, or 0 if there are no further environments }; ////////////////////// built-in primitive procedures cell proc_add(const cells & c) { long n(atol(c[0].val.c_str())); for (cellit i = c.begin()+1; i != c.end(); ++i) n += atol(i->val.c_str()); return cell(Number, str(n)); } cell proc_sub(const cells & c) { long n(atol(c[0].val.c_str())); for (cellit i = c.begin()+1; i != c.end(); ++i) n -= atol(i->val.c_str()); return cell(Number, str(n)); } cell proc_mul(const cells & c) { long n(1); for (cellit i = c.begin(); i != c.end(); ++i) n *= atol(i->val.c_str()); return cell(Number, str(n)); } cell proc_div(const cells & c) { long n(atol(c[0].val.c_str())); for (cellit i = c.begin()+1; i != c.end(); ++i) n /= atol(i->val.c_str()); return cell(Number, str(n)); } cell proc_greater(const cells & c) { long n(atol(c[0].val.c_str())); for (cellit i = c.begin()+1; i != c.end(); ++i) if (n <= atol(i->val.c_str())) return false_sym; return true_sym; } cell proc_less(const cells & c) { long n(atol(c[0].val.c_str())); for (cellit i = c.begin()+1; i != c.end(); ++i) if (n >= atol(i->val.c_str())) return false_sym; return true_sym; } cell proc_less_equal(const cells & c) { long n(atol(c[0].val.c_str())); for (cellit i = c.begin()+1; i != c.end(); ++i) if (n > atol(i->val.c_str())) return false_sym; return true_sym; } cell proc_length(const cells & c) { return cell(Number, str(c[0].list.size())); } cell proc_nullp(const cells & c) { return c[0].list.empty() ? true_sym : false_sym; } cell proc_car(const cells & c) { return c[0].list[0]; } cell proc_cdr(const cells & c) { if (c[0].list.size() < 2) return nil; cell result(c[0]); result.list.erase(result.list.begin()); return result; } cell proc_append(const cells & c) { cell result(List); result.list = c[0].list; for (cellit i = c[1].list.begin(); i != c[1].list.end(); ++i) result.list.push_back(*i); return result; } cell proc_cons(const cells & c) { cell result(List); result.list.push_back(c[0]); for (cellit i = c[1].list.begin(); i != c[1].list.end(); ++i) result.list.push_back(*i); return result; } cell proc_list(const cells & c) { cell result(List); result.list = c; return result; } // define the bare minimum set of primintives necessary to pass the unit tests void add_globals(environment & env) { env["nil"] = nil; env["#f"] = false_sym; env["#t"] = true_sym; env["append"] = cell(&proc_append); env["car"] = cell(&proc_car); env["cdr"] = cell(&proc_cdr); env["cons"] = cell(&proc_cons); env["length"] = cell(&proc_length); env["list"] = cell(&proc_list); env["null?"] = cell(&proc_nullp); env["+"] = cell(&proc_add); env["-"] = cell(&proc_sub); env["*"] = cell(&proc_mul); env["/"] = cell(&proc_div); env[">"] = cell(&proc_greater); env["<"] = cell(&proc_less); env["<="] = cell(&proc_less_equal); } ////////////////////// eval cell eval(cell x, environment * env) { if (x.type == Symbol) return env->find(x.val)[x.val]; if (x.type == Number) return x; if (x.list.empty()) return nil; if (x.list[0].type == Symbol) { if (x.list[0].val == "quote") // (quote exp) return x.list[1]; if (x.list[0].val == "if") // (if test conseq [alt]) return eval(eval(x.list[1], env).val == "#f" ? (x.list.size() < 4 ? nil : x.list[3]) : x.list[2], env); if (x.list[0].val == "set!") // (set! var exp) return env->find(x.list[1].val)[x.list[1].val] = eval(x.list[2], env); if (x.list[0].val == "define") // (define var exp) return (*env)[x.list[1].val] = eval(x.list[2], env); if (x.list[0].val == "lambda") { // (lambda (var*) exp) x.type = Lambda; // keep a reference to the environment that exists now (when the // lambda is being defined) because that's the outer environment // we'll need to use when the lambda is executed x.env = env; return x; } if (x.list[0].val == "begin") { // (begin exp*) for (size_t i = 1; i < x.list.size() - 1; ++i) eval(x.list[i], env); return eval(x.list[x.list.size() - 1], env); } } // (proc exp*) cell proc(eval(x.list[0], env)); cells exps; for (cell::iter exp = x.list.begin() + 1; exp != x.list.end(); ++exp) exps.push_back(eval(*exp, env)); if (proc.type == Lambda) { // Create an environment for the execution of this lambda function // where the outer environment is the one that existed* at the time // the lambda was defined and the new inner associations are the // parameter names with the given arguments. // *Although the environmet existed at the time the lambda was defined // it wasn't necessarily complete - it may have subsequently had // more symbols defined in that environment. return eval(/*body*/proc.list[2], new environment(/*parms*/proc.list[1].list, /*args*/exps, proc.env)); } else if (proc.type == Proc) return proc.proc(exps); std::cout << "not a function\n"; exit(1); } ////////////////////// parse, read and user interaction // convert given string to list of tokens std::list<std::string> tokenize(const std::string & str) { std::list<std::string> tokens; const char * s = str.c_str(); while (*s) { while (*s == ' ') ++s; if (*s == '(' || *s == ')') tokens.push_back(*s++ == '(' ? "(" : ")"); else { const char * t = s; while (*t && *t != ' ' && *t != '(' && *t != ')') ++t; tokens.push_back(std::string(s, t)); s = t; } } return tokens; } // numbers become Numbers; every other token is a Symbol cell atom(const std::string & token) { if (isdig(token[0]) || (token[0] == '-' && isdig(token[1]))) return cell(Number, token); return cell(Symbol, token); } // return the Lisp expression in the given tokens cell read_from(std::list<std::string> & tokens) { const std::string token(tokens.front()); tokens.pop_front(); if (token == "(") { cell c(List); while (tokens.front() != ")") c.list.push_back(read_from(tokens)); tokens.pop_front(); return c; } else return atom(token); } // return the Lisp expression represented by the given string cell read(const std::string & s) { std::list<std::string> tokens(tokenize(s)); return read_from(tokens); } // convert given cell to a Lisp-readable string std::string to_string(const cell & exp) { if (exp.type == List) { std::string s("("); for (cell::iter e = exp.list.begin(); e != exp.list.end(); ++e) s += to_string(*e) + ' '; if (s[s.size() - 1] == ' ') s.erase(s.size() - 1); return s + ')'; } else if (exp.type == Lambda) return "<Lambda>"; else if (exp.type == Proc) return "<Proc>"; return exp.val; } // the default read-eval-print-loop void repl(const std::string & prompt, environment * env) { for (;;) { std::cout << prompt; std::string line; std::getline(std::cin, line); std::cout << to_string(eval(read(line), env)) << '\n'; } } int main () { environment global_env; add_globals(global_env); repl("90> ", &global_env); }

With Lis.py to guide me writing this was fairly straight-forward, with two exceptions. The first point I had to stop and think was in eval() when the symbol to be evaluated was "lambda", i.e. at the point of definition of the lambda. In Peter's code he returns a Python lambda; not something available to me. Then I realised that I didn't have to actually do anything with the lambda body, just keep it around until it needs to be executed. That's why I can just change the cell type from Symbol to Lambda and return it as-is.

The second pause for thought was much longer; this time it was at the point of execution of the lambda. Partly because I don't know Python (or Scheme) it wasn't clear to me what was going on with the environment. The problem was that lambdas that returned lambdas didn't work: variables that were defined at the time the lambda was returned were not defined at the time that returned lambda was executed.

It took a little while to work through the problem, but eventually I did. It helped to look at some simple examples to see where things went wrong. Here is my program executing some sample code adapted from an article that appeared in February 1988 Byte magazine:

90> (define multiply-by (lambda (n) (lambda (y) (* y n)))) <Lambda> 90> (define doubler (multiply-by 2)) <Lambda> 90> (define tripler (multiply-by 3)) <Lambda> 90> (doubler 4) 8 90> (tripler 4) 12 90>

Clearly, doubler is not only associated with the procedure (lambda (y) (* y n)) but it must also have access to an environment where the value of n is 2.

I added some code to the start of the eval function to dump out the value of the paramaters x and env each time it is called. Here is the output while executing some of the above sample code.

eval("(define multiply-by (lambda (n) (lambda (y) (* y n))))", [global]) eval("(lambda (n) (lambda (y) (* y n)))", [global]) -> <Lambda>(lambda (n) (lambda (y) (* y n)))+ref[global] -> <Lambda>(lambda (n) (lambda (y) (* y n)))+ref[global] eval("(define doubler (multiply-by 2))", [global]) eval("(multiply-by 2)", [global]) eval("multiply-by", [global]) -> <Lambda>(lambda (n) (lambda (y) (* y n)))+ref[global] eval("2", [global]) -> 2 ; execute the <Lambda>(lambda (n) (lambda (y) (* y n)))+ref[global], which involves ; creating a new environment containing [n->2] with an outer environment of [global] ; and then calling eval with (lambda (y) (* y n)) eval("(lambda (y) (* y n))", [n->2 [global]]) -> <Lambda>(lambda (y) (* y n))+ref[n->2 [global]] -> <Lambda>(lambda (y) (* y n))+ref[n->2 [global]] -> <Lambda>(lambda (y) (* y n))+ref[n->2 [global]] eval("(doubler 4)", [global]) eval("doubler", [global]) -> <Lambda>(lambda (y) (* y n))+ref[n->2 [global]] eval("4", [global]) -> 4 ; execute the <Lambda>(lambda (y) (* y n))+ref[n->2 [global]], which involves ; creating a new environment containing [y->4] with an outer environment of [n->2 [global]] ; and then calling eval with (* y n) eval("(* y n)", [y->4 [n->2 [global]]]) eval("*", [y->4 [n->2 [global]]]) -> proc_mul eval("y", [y->4 [n->2 [global]]]) -> 4 eval("n", [y->4 [n->2 [global]]]) -> 2 proc_mul(4, 2) -> 8 -> 8 -> 8

"[global]" means the global environment where "*" maps to the built-in proc_mul, etc.

"[y->4 [n->2 [global]]]" means an innermost environment where y maps to 4, that environment's outer environment where n maps to 2 and that environemt's outer environment, which is the global environment.

When looking up the value of a variable the code starts with the innermost environment and if the variable is not defined there it tries the next outer environment and so on.


I don't know whether I've explained that clearly enough to make sense. The important bit I realised is that a new environment must be created when a lambda is evaluated containing (a) all the paramater->argument associations, and (b) this new environment's outer environment must be the reference to the environment that existed at the time the lambda was defined. I believe this is called a lexical closure.

Here's my program executing a another example I like, this time adapted from that Wikipedia article on lexical closures. It just underlines that the closure captures the variable, not just the value of the variable, and that the captured variable may be changed.

90> (define count-down-from (lambda (n) (lambda () (set! n (- n 1))))) <Lambda> 90> (define count-down-from-3 (count-down-from 3)) <Lambda> 90> (define count-down-from-4 (count-down-from 4)) <Lambda> 90> (count-down-from-3) 2 90> (count-down-from-4) 3 90> (count-down-from-3) 1 90> (count-down-from-3) 0 90> (count-down-from-4) 2 90> (count-down-from-4) 1 90> (count-down-from-4) 0 90>

Here is another example, again adapted from the Wikipedia article on closures. This demonstrates that not only can the closure capture existing variables, it also captures variables created inside the closure (the variable hidden in this case). Also in this example, two procedures are created that share the same closure. (I spread some of the code over several lines to make it more readable; it has to be entered all on one line for my primitive program.)

90> (define set-hidden 0) 0 90> (define get-hidden 0) 0 90> ((lambda () (begin (define hidden 0) (set! set-hidden (lambda (n) (set! hidden n))) (set! get-hidden (lambda () hidden))))) <Lambda> 90> (get-hidden) 0 90> (set-hidden 1234) 1234 90> (get-hidden) 1234 90> hidden unbound symbol 'hidden'

Testing

Here are the 29 tests for Lis.py. The main() function in the code above is replaced by all this code to run the tests.

////////////////////// unit tests unsigned g_test_count; // count of number of unit tests executed unsigned g_fault_count; // count of number of unit tests that fail template <typename T1, typename T2> void test_equal_(const T1 & value, const T2 & expected_value, const char * file, int line) { ++g_test_count; if (value != expected_value) { std::cout << file << '(' << line << ") : " << " expected " << expected_value << ", got " << value << '\n'; ++g_fault_count; } } // write a message to std::cout if value != expected_value #define TEST_EQUAL(value, expected_value) test_equal_(value, expected_value, __FILE__, __LINE__) // evaluate the given Lisp expression and compare the result against the given expected_result #define TEST(expr, expected_result) TEST_EQUAL(to_string(eval(read(expr), &global_env)), expected_result) int main () { environment global_env; add_globals(global_env); // the 29 unit tests for lis.py TEST("(quote (testing 1 (2.0) -3.14e159))", "(testing 1 (2.0) -3.14e159)"); TEST("(+ 2 2)", "4"); TEST("(+ (* 2 100) (* 1 10))", "210"); TEST("(if (> 6 5) (+ 1 1) (+ 2 2))", "2"); TEST("(if (< 6 5) (+ 1 1) (+ 2 2))", "4"); TEST("(define x 3)", "3"); TEST("x", "3"); TEST("(+ x x)", "6"); TEST("(begin (define x 1) (set! x (+ x 1)) (+ x 1))", "3"); TEST("((lambda (x) (+ x x)) 5)", "10"); TEST("(define twice (lambda (x) (* 2 x)))", "<Lambda>"); TEST("(twice 5)", "10"); TEST("(define compose (lambda (f g) (lambda (x) (f (g x)))))", "<Lambda>"); TEST("((compose list twice) 5)", "(10)"); TEST("(define repeat (lambda (f) (compose f f)))", "<Lambda>"); TEST("((repeat twice) 5)", "20"); TEST("((repeat (repeat twice)) 5)", "80"); TEST("(define fact (lambda (n) (if (<= n 1) 1 (* n (fact (- n 1))))))", "<Lambda>"); TEST("(fact 3)", "6"); //TEST("(fact 50)", "30414093201713378043612608166064768844377641568960512000000000000"); TEST("(fact 12)", "479001600"); // no bignums; this is as far as we go with 32 bits TEST("(define abs (lambda (n) ((if (> n 0) + -) 0 n)))", "<Lambda>"); TEST("(list (abs -3) (abs 0) (abs 3))", "(3 0 3)"); TEST("(define combine (lambda (f)" "(lambda (x y)" "(if (null? x) (quote ())" "(f (list (car x) (car y))" "((combine f) (cdr x) (cdr y)))))))", "<Lambda>"); TEST("(define zip (combine cons))", "<Lambda>"); TEST("(zip (list 1 2 3 4) (list 5 6 7 8))", "((1 5) (2 6) (3 7) (4 8))"); TEST("(define riff-shuffle (lambda (deck) (begin" "(define take (lambda (n seq) (if (<= n 0) (quote ()) (cons (car seq) (take (- n 1) (cdr seq))))))" "(define drop (lambda (n seq) (if (<= n 0) seq (drop (- n 1) (cdr seq)))))" "(define mid (lambda (seq) (/ (length seq) 2)))" "((combine append) (take (mid deck) deck) (drop (mid deck) deck)))))", "<Lambda>"); TEST("(riff-shuffle (list 1 2 3 4 5 6 7 8))", "(1 5 2 6 3 7 4 8)"); TEST("((repeat riff-shuffle) (list 1 2 3 4 5 6 7 8))", "(1 3 5 7 2 4 6 8)"); TEST("(riff-shuffle (riff-shuffle (riff-shuffle (list 1 2 3 4 5 6 7 8))))", "(1 2 3 4 5 6 7 8)"); std::cout << "total tests " << g_test_count << ", total failures " << g_fault_count << "\n"; return g_fault_count ? EXIT_FAILURE : EXIT_SUCCESS; }

All 29 tests pass. Goal 1 achieved.

Goal 2: I'm not counting blank lines or comment-only lines, and I'm not counting lines that contain only an opening or closing curly brace, because I'm just not counting them.

bash$ grep -v "^ *$\|^ *//\|^ *[}{] *$" lisp.cpp | wc 198 953 8256

Not quite 90. But south of 200 isn't bad, is it? (Just to be clear: I'm not claiming I've produced the equivalent of Lis.py in under 200 lines of C++.)


Conclusion

Compared with Lis.py my effort is incomplete, inefficient and leaks memory. Unlike some of the code I've presented in other blog posts the end result here is not useful in itself; it was the process of developing it that was useful, if only for me.

Nevertheless, I get a little thrill out of having made something that allows me to type (define cube (lambda (n) (* n n n))) and then (cube 3). It's like magic.

EDIT June 2013: Since I published this post it has been viewed 37,561 times, which is a big deal for me. Occasionally someone will ask me if I'll allow the code to be used for their project and I always say yes. To make it simpler I've removed the copyright and placed it in the public domain.

index of blog posts

Why?

One of the questions I'm never asked is "why did you call your blog How to Write a Program?" The answer I would give is the slightly flippant "they say you teach what you need to learn."

Actually, I'm not sure I like the name any more. I think at the time I wanted something simple and straight-forward. It isn't meant to be ironic!

(EDIT: I should also have said that the idea came from the title of an article written by Ian Fleming: How to Write a Thriller.)

I've been programming since I was 16 years old. I enjoy writing code. I write code for nothing, like I did when I was 16, as well as writing code for a living. I hope to be writing code on the day I die.

index of blog posts

Write a C function taking two strings...

A guy called Tommy M. McGuire attended an interview with Google and was asked to write some code on the whiteboard:

My big question: "Write a C function taking two strings and returning a string containing one copy of the characters that occur in both." Hint: Spend some time looking at one of the strings and use an array of flags.

Given that hint, I guess we can assume the strings contain only 8-bit single-byte characters and the sort of thing the Google interviewers might have been looking for was something like this:

// return one copy of all chars that occur in both 'a' and 'b' // e.g. common_chars("common", "man") -> "mn" std::string common_chars(const char * a, const char * b) { std::string result; char occurs_in_a[UCHAR_MAX + 1] = {0}; // set occurs_in_a[c] to 1 for all values of c that occur in string a while (*a) occurs_in_a[static_cast<unsigned char>(*a++)] = 1; // check every character in b to see if it also occurs in a for (; *b; ++b) { if (occurs_in_a[static_cast<unsigned char>(*b)]) { result += *b; // add char to the result occurs_in_a[static_cast<unsigned char>(*b)] = 0; // never add it again } } return result; }

Yes, I wrote it in C++. (I'm the kind of guy Linus Torvalds loves to hate and Peter Seibel doesn't understand.) So how would we get the result back to the caller in C? I can think of about a dozen ways, all of which are also available to me in C++, and all of which are more tedious and error-prone both for the implementation and for the callers of the function. Of course, if it made sense to use one of those methods in the context in which this function was to operate, then I would use it.

Going back to the whiteboard: if I was standing in front of a hyper-intelligent Googler I would probably wet my pants and I suspect I would have written the function differently: I wouldn’t have commented it; I probably would have written 256 instead of UCHAR_MAX + 1; more seriously, I may have forgotten to cast away the (possible) sign of the char when used as an array index. All of these things would have occurred to me only after I'd left the building. (And, since the requirement was for a C function, I guess I would have had to fiddle around with buffers and buffer sizes and null terminators and shit.)

In the real world I would unit test this function with something like this:

// return true iff 'a' and 'b' contain exactlty the same characters // ignoring the character ordering; e.g. same("ab", "ba") -> true bool same(const std::string & a, const std::string & b) { std::vector<char> va(a.c_str(), a.c_str() + a.size()); std::sort(va.begin(), va.end()); std::vector<char> vb(b.c_str(), b.c_str() + b.size()); std::sort(vb.begin(), vb.end()); return va == vb; } int main() { char all_chars[256]; for (int i = 0; i < 256; ++i) all_chars[i] = static_cast<unsigned char>(i + 1); struct test { const char * a; const char * b; const char * expected; }; const test table[] = { {"", "", ""}, {"a", "", ""}, {"", "a", ""}, {"a", "b", ""}, {"a", "a", "a"}, {"a", "aaa", "a"}, {"aaa", "a", "a"}, {"a", "ab", "a"}, {"b", "ab", "b"}, {"ab", "a", "a"}, {"ab", "b", "b"}, {"ab", "ab", "ab"}, {"ab", "ba", "ab"}, {"ab", "cat", "a"}, {"ab", "abba", "ab"}, {"abba", "abba", "ab"}, {"aabbcc", "cab", "abc"}, {"cab", "abcabc", "abc"}, {"common", "man", "mn"}, {"man", "common", "mn"}, {"fox", "in socks", "o"}, {"play", "misty", "y"}, {"the rain", "in spain", " ain"}, {"don't you know", "you'll stain the", "you' tn"}, {"Transmission", "C++", ""}, {all_chars, "ABC", "ABC"}, {"ABC", all_chars, "ABC"}, {all_chars, all_chars, all_chars}, {0, 0, 0} // end of table }; int tests(0), failures(0); for (const test * t = table; t->a; ++t) { ++tests; const std::string result(common_chars(t->a, t->b)); if (!same(result, t->expected)) { ++failures; std::cout << "Failed for f('" << t->a << "', '" << t->b << "') expected '" << t->expected << "' got '" << result << "'\n"; } } std::cout << "total tests " << tests << ", total failures " << failures << "\n"; return failures ? EXIT_FAILURE : EXIT_SUCCESS; }

I've been writing code for a long time - long enough to know that I make mistakes. I have found unit tests to be an excellent way to pick up some of those mistakes as well as being useful for other reasons I'll write about another time.

Of course, passing a bunch of unit tests does not mean the code doesn't have horrible bugs in it. For example, I tested this code under a compiler where chars are signed. If you remove the static_cast<unsigned char>() casts the unit tests still all pass. What this means is that when *a is '\x80' the expression occurs_in_a[*a++] = 1 is similar to occurs_in_a[-128] = 1 and this sets a byte to 1 on the stack 128 bytes before the occurs_in_a array. But that's alright (NOT!) because if (occurs_in_a[*b]) will look for it in the same place, and find it there, which is why the tests still pass. But the stack is now corrupted, the consequences of which may be nil or catastrophic, immediate or postponed.

index of blog posts

Einstein's Riddle

Here’s a sucky program I wrote to solve Einstein’s Riddle, which has nothing to do with Einstein. It is many, many times slower than other much better solutions.

Perhaps 'sucky' is a bit harsh. In its favor I believe it to be correct: it cycles through all 24,883,200,000 (= 5^5 x 4^5 x 3^5 x 2^5 x 1^5) possible solutions and finds the one and only combination that satisfies all the requirements. It is also a straight-forward representation of the stated riddle, and was therefore quick to write. On the downside, it does take 10 minutes to find the solution, which does not compare well with the solutions referred to above.

// Anthony C. Hay - Find the solution to Einstein's riddle. (slow & prosaic) // See http://en.wikipedia.org/wiki/Zebra_Puzzle // and http://weitz.de/einstein.html #include <iostream> #include <algorithm> namespace { // the possible values of the five variables enum nation { british, swedish, norwegian, german, danish }; enum colour { red, green, yellow, blue, white }; enum animal { dog, horse, cat, bird, fish }; enum cigarette { marlboro, winfield, rothmans, pallmall, dunhill }; enum drink { tea, coffee, milk, beer, water }; // these are for printing the results; obviously the order must correspond to the enums above const char * nation_names[] = { "british", "swedish", "norwegian", "german", "danish" }; const char * colour_names[] = { "red", "green", "yellow", "blue", "white" }; const char * animal_names[] = { "dog", "horse", "cat", "bird", "fish" }; const char * cigarette_names[] = { "marlboro", "winfield", "rothmans", "pallmall", "dunhill" }; const char * drink_names[] = { "tea", "coffee", "milk", "beer", "water" }; // arbitrarily assign the leftmost house an index of 0, and the rightmost 4; // e.g. the nationality of the owner of the left-most house would be given by // nations[0], and the pet he keeps would be given by animals[0], and the pet // his neighbour (on his right) keeps would be given by animals[1], and so on const int num_houses = 5; nation nations[num_houses]; colour colours[num_houses]; animal animals[num_houses]; cigarette cigarettes[num_houses]; drink drinks[num_houses]; // set 'array' to first permutation, which is numerically { 0, 1, 2, 3, 4 } template <class T, size_t size> void init(T (& array)[size]) { for (int i = 0; i < size; ++i) array[i] = static_cast<T>(i); } // set 'array' to next permutation if possible, otherwise return false template <class T, size_t size> bool next_permutation(T (& array)[size]) { return std::next_permutation(array, array + size); } // set the combination of all house variables to the next permutation bool permute() { if (next_permutation(nations)) return true; init(nations); if (next_permutation(colours)) return true; init(colours); if (next_permutation(animals)) return true; init(animals); if (next_permutation(cigarettes)) return true; init(cigarettes); if (next_permutation(drinks)) return true; init(drinks); // we have cycled through all permutations of all variables return false; } // return the number of the house of the given colour inline int find_colour(colour c) { int i = 0; while (colours[i] != c) ++i; return i; } // return the number of the house whose owner is of the given nationality inline int find_nation(nation n) { int i = 0; while (nations[i] != n) ++i; return i; } // return the number of the house whose owner smokes the given brand of cigarette inline int find_cigarette(cigarette c) { int i = 0; while (cigarettes[i] != c) ++i; return i; } // the Norwegian lives next to the blue house inline bool norwegian_lives_next_to_blue_house() { const int i = find_nation(norwegian); return (i > 0 && colours[i-1] == blue) || (i < (num_houses - 1) && colours[i+1] == blue); } // the green house is on the left of the white house inline bool green_left_of_white() { const int i = find_colour(green); return i < (num_houses - 1) && colours[i+1] == white; } // the person who smokes Marlboro lives next to the one who keeps cats inline bool smokes_marlboro_next_cats() { const int i = find_cigarette(marlboro); return (i > 0 && animals[i-1] == cat) || (i < (num_houses - 1) && animals[i+1] == cat); } // the person who keeps horses lives next to the person who smokes Dunhill inline bool smokes_dunhill_next_horses() { const int i = find_cigarette(dunhill); return (i > 0 && animals[i-1] == horse) || (i < (num_houses - 1) && animals[i+1] == horse); } // the person who smokes Marlboro has a neigbor who drinks water inline bool smokes_marlboro_next_water() { const int i = find_cigarette(marlboro); return (i > 0 && drinks[i-1] == water) || (i < (num_houses - 1) && drinks[i+1] == water); } // return true iff all the stated conditions are met bool is_solution() { return // the Norwegian lives in the first house nations[0] == norwegian // the man living in the centre house drinks milk && drinks[num_houses/2] == milk // the Brit lives in the red house && colours[find_nation(british)] == red // the Swede keeps dogs as pets && animals[find_nation(swedish)] == dog // the Dane drinks tea && drinks[find_nation(danish)] == tea // the German smokes Rothmans && cigarettes[find_nation(german)] == rothmans // the green house's owner drinks coffee && drinks[find_colour(green)] == coffee // the owner of the yellow house smokes Dunhill && cigarettes[find_colour(yellow)] == dunhill // the person who smokes Pall Mall rears birds && animals[find_cigarette(pallmall)] == bird // the person who smokes Winfield drinks beer && drinks[find_cigarette(winfield)] == beer && norwegian_lives_next_to_blue_house() && green_left_of_white() && smokes_marlboro_next_cats() && smokes_dunhill_next_horses() && smokes_marlboro_next_water(); } // print the details for all houses void print() { std::cout << '\n'; for (int i = 0; i < num_houses; ++i) std::cout << "house " << i + 1 << ' ' << colour_names[colours[i]] << ' ' << nation_names[nations[i]] << ' ' << animal_names[animals[i]] << ' ' << cigarette_names[cigarettes[i]] << ' ' << drink_names[drinks[i]] << "\n"; } }//anonymous namespace int main () { init(nations); init(colours); init(animals); init(cigarettes); init(drinks); if (is_solution()) print(); while (permute()) { if (is_solution()) print(); } }

Update November 2013:

I wanted to create a solution that was nearer to the performance of Edi Weitz’s Lisp code, referred to above. Here is what I came up with:

// Anthony C. Hay - Find the solution to Einstein's riddle. (better) // See http://howtowriteaprogram.blogspot.co.uk/2009/07/einsteins-riddle.html // // Compile with // g++ -O3 -o einstine einstine.cpp // or, with MSVC // cl /nologo /EHs /O2 einstine.cpp #include <iostream> #include <algorithm> namespace { const int num_houses = 5; const int num_unique_values = 5; // the possible values of the five attributes enum nation { british, swedish, norwegian, german, danish }; enum colour { red, green, yellow, blue, white }; enum animal { dog, horse, cat, bird, fish }; enum cigarette { marlboro, winfield, rothmans, pallmall, dunhill }; enum drink { tea, coffee, milk, beer, water }; // these are for printing the results; obviously the order must correspond to the enums above const char * nation_names[num_unique_values] = { "british", "swedish", "norwegian", "german", "danish" }; const char * colour_names[num_unique_values] = { "red", "green", "yellow", "blue", "white" }; const char * animal_names[num_unique_values] = { "dog", "horse", "cat", "bird", "fish" }; const char * cigarette_names[num_unique_values] = { "marlboro", "winfield", "rothmans", "pallmall", "dunhill" }; const char * drink_names[num_unique_values] = { "tea", "coffee", "milk", "beer", "water" }; // print the details for all houses void print(const int * nations, const int * drinks, const int * colours, const int * cigarettes, const int * animals) { std::cout << '\n'; for (int i = 0; i < num_houses; ++i) std::cout << "house " << i + 1 << ' ' << colour_names[colours[i]] << ' ' << nation_names[nations[i]] << ' ' << animal_names[animals[i]] << ' ' << cigarette_names[cigarettes[i]] << ' ' << drink_names[drinks[i]] << "\n"; } // create a lookup 'table' for given 'perm' such that // table[n] -> number of house with attribute n // // e.g. if p is {2, 3, 4, 1, 0} then mk_lookup_table(p, t) will // initialise t to {4, 3, 0, 1, 2} so we can ask "where is 1?" // like this, t[1], and get the answer 3 inline void mk_lookup_table(const int * perm, int * table) { for (int i = 0; i < num_unique_values; ++i) table[perm[i]] = i; } // return true iff the house either side of 'house_number' is/has 'desired_value' inline bool neighbour(int house_number, const int * attributes, int desired_value) { return house_number > 0 && attributes[house_number - 1] == desired_value || house_number < num_unique_values-1 && attributes[house_number + 1] == desired_value; } // each of these possible() functions returns false if the given information is // sufficient to eliminate the branch from the search space, otherwise it returns // true, which means we don't yet have enough information to eliminate the branch // test the given permutation of the nations attribute and reject it (return false) // if it is definitely not on the branch leading to a solution inline bool possible(const int * nations) { // with our very limited information we can test only that... // the Norwegian lives in the first house return nations[0] == norwegian; } inline bool possible(const int * nations, const int * drinks) { int nationalities[num_unique_values]; mk_lookup_table(nations, nationalities); return // the man living in the centre house drinks milk drinks[num_houses/2] == milk // the Dane drinks tea && drinks[nationalities[danish]] == tea; } inline bool possible(const int * nations, const int * drinks, const int * colours) { int nationalities[num_unique_values]; mk_lookup_table(nations, nationalities); int house_colours[num_unique_values]; mk_lookup_table(colours, house_colours); return // the Brit lives in the red house colours[nationalities[british]] == red // the green house's owner drinks coffee && drinks[house_colours[green]] == coffee // the green house is on the left of the white house && (house_colours[green] < num_unique_values-1 && colours[house_colours[green]+1] == white) // the Norwegian lives next to the blue house && neighbour(nationalities[norwegian], colours, blue); } inline bool possible(const int * nations, const int * drinks, const int * colours, const int * cigarettes) { int nationalities[num_unique_values]; mk_lookup_table(nations, nationalities); int house_colours[num_unique_values]; mk_lookup_table(colours, house_colours); int smokes[num_unique_values]; mk_lookup_table(cigarettes, smokes); return // the German smokes Rothmans cigarettes[nationalities[german]] == rothmans // the owner of the yellow house smokes Dunhill && cigarettes[house_colours[yellow]] == dunhill // the person who smokes Winfield drinks beer && drinks[smokes[winfield]] == beer; } inline bool possible(const int * nations, const int * drinks, const int * /*colours*/, const int * cigarettes, const int * animals) { int nationalities[num_unique_values]; mk_lookup_table(nations, nationalities); int smokes[num_unique_values]; mk_lookup_table(cigarettes, smokes); int pets[num_unique_values]; mk_lookup_table(animals, pets); return // the Swede keeps dogs as pets animals[nationalities[swedish]] == dog // the person who smokes Pall Mall rears birds && animals[smokes[pallmall]] == bird // the person who smokes Marlboro lives next to the one who keeps cats && neighbour(smokes[marlboro], animals, cat) // the person who keeps horses lives next to the person who smokes Dunhill && neighbour(pets[horse], cigarettes, dunhill) // the person who smokes Marlboro has a neigbor who drinks water && neighbour(smokes[marlboro], drinks, water); } // search for all possible solutions and print each one found (there is only one) void solve() { // Each attribute has 5 unique values. E.g. there are five colours. // Here we create one table of all permutations of 5 unique values. // Then the current permutation of all five attributes may be // maintained with five simple indexes into this one table. const int num_permutations = 120; // = num_unique_values! = 5! int ptab[num_permutations][num_unique_values]; int values[num_unique_values] = {0, 1, 2, 3, 4}; for (int i = 0; i < num_permutations; ++i) { std::copy(values, values + num_unique_values, ptab[i]); std::next_permutation(values, values + num_unique_values); } // each for loop cycles through every permutation of one of the attributes; // each if tests whether it's worth looking further down that branch of the search space for (int nation = 0; nation < num_permutations; ++nation) if (possible(ptab[nation])) for (int drink = 0; drink < num_permutations; ++drink) if (possible(ptab[nation], ptab[drink])) for (int colour = 0; colour < num_permutations; ++colour) if (possible(ptab[nation], ptab[drink], ptab[colour])) for (int cigarette = 0; cigarette < num_permutations; ++cigarette) if (possible(ptab[nation], ptab[drink], ptab[colour], ptab[cigarette])) for (int animal = 0; animal < num_permutations; ++animal) if (possible(ptab[nation], ptab[drink], ptab[colour], ptab[cigarette], ptab[animal])) print(ptab[nation], ptab[drink], ptab[colour], ptab[cigarette], ptab[animal]); } }//anonymous namespace int main() { solve(); /* expected output: house 1 yellow norwegian cat dunhill water house 2 blue danish horse marlboro tea house 3 red british bird pallmall milk house 4 green german fish rothmans coffee house 5 white swedish dog winfield beer */ }

Notes:

- Let's call my original code Einstine09 and my new code Einstine13.

- Einstine13 run time is 0.012s (real 0.012s, user 0.001s, sys 0.002s) on a 2.8GHz Intel E8235 processor. (But an "int main() {}" runs in 0.010s (real), so should we subtract that from 0.012s and call it 2ms? I'm not sure. It doesn't really matter; what matters is that Einstine13 is in the same ballpark as the fastest solutions given by others, and not in the next county as Einstine09 was.) Einstine09 runs in 350.808s (real) on the same machine, compiled with the same compiler and -O3 option. Choosing a better algorithm gave us a 30,000× speed improvement (350.808 / 0.012 = 29,234).

- There are 5 different attributes (such as colour, nationality) and each attribute has 5 unique values. There are 5! permutations of 5 unique values so the total number of possible solution states is (5!)⁵ = 24,883,200,000. Einstine09 calls is_solution() for each and every one of these states and is sloooow. Einstine13 calls the possible() functions a total of just 18,360 times and is much faster.

- I knew the problem was one of combinatorial search, like the eight queens problem. But I couldn’t see how to prune the search tree by applying all the rules at each branch because a rule might refer to something that hadn’t yet been decided: you can’t chop off a branch where the Winfield smoker doesn’t drink beer if you don’t yet know who the Winfield smoker is. And so on. My personal aha! moment came while reading Edi Weitz’s explanation of his Lisp solution: “Note that every condition has to return T if [...] not all of its parameters are defined yet.” Yes, it’s obvious to me too, now.

- Reading Edi Weitz’s commentary gave me one of the clearest glimpses I’ve had of the secret ingredient in Lisp and I recommend it to anyone struggling to understand why so many Lisp cognoscenti rave about the language. But I have to say that without his explanation I think I would have struggled to understand his code. My C++ solution is fast, but it's specific to solving the Einstein problem. Dr. Weitz's Lisp solution is also fast, but in more-or-less the same amount of code he has created a domain-specific language for solving any Einstine-like problem. Thank you Dr. Weitz for sharing it.

index of blog posts

Lutz Prechelt's Language Comparison

About a decade ago Lutz Prechelt conducted a study to compare various computer languages, including C, C++, Java and Python. In the study he asked about 70 different programmers to code their own implementation of a given set of requirements. You can read all about it here. I think the most interesting conclusion he draws is that

“Interpersonal variability, that is the capability and behavior differences between programmers using the same language, tends to account for more differences between programs than a change of the programming language.”

Over the years some similar studies were done for other languages and various individuals have taken up the challenge using the language of their choice; D, for example. So I thought I’d give it a go (see below). Note that I wrote this in the context of a challenge where keeping the number of lines of code to a minimum was more in my mind than usual. For example, code I usually work on would need to take some action if an attempted file open failed.

I’m rather pleased that my 49 line C++ effort is only 4 lines longer than the great Peter Norvig’s Lisp version.

It signifies not much; it’s just a bit of fun. If you want to try it you’ll need the data sets. My output is the same as the expected output, but in a different order, which you may verify with sort and diff.

// Anthony C. Hay - my implementation of Lutz Prechelt's requirements // see http://page.mi.fu-berlin.de/prechelt/Biblio/jccpprtTR.pdf // and http://www.flownet.com/ron/papers/lisp-java/ // and http://www.norvig.com/java-lisp.html // and http://www.digitalmars.com/d/lisp-java-d.html #include <iostream> #include <fstream> #include <string> #include <vector> #include <map> // word_map: the key is the sequence of digits that encodes // all the words in the associated vector typedef std::vector<std::string> words; typedef std::map<std::string, words> word_map; // return digit associated with given letter 'ch' (must be in a..z or A..Z) char encode(char ch) { /* E | J N Q | R W X | D S Y | F T | A M | C I V | B K U | L O P | G H Z e | j n q | r w x | d s y | f t | a m | c i v | b k u | l o p | g h z 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 */ return "57630499617851881234762239"[toupper(ch) - 'A']; } // return digit sequence corresponding to given 'word' std::string encode(const std::string & word) { std::string encoded_word; for (const char * p = word.c_str(); *p; ++p) { if (*p != '"') // ignore embedded double quotes (umlauts) encoded_word += encode(*p); } return encoded_word; } // return the word map for dict.txt word_map read_words() { word_map wp; std::ifstream is("dictionary.txt"); std::string word; while (std::getline(is, word)) wp[encode(word)].push_back(word); return wp; } // return the given number with all the non-digit characters removed std::string filtered(const std::string & num) { std::string result; for (const char * p = num.c_str(); *p; ++p) { if (isdigit(*p)) result += *p; } return result; } // the (messy) heart: find and print the sentences void find_sentences(const word_map & dict, const std::string & rawnum, const std::string & num, const std::string & sentence, bool trailing_digit) { if (num.empty()) { if (!sentence.empty()) std::cout << rawnum << ":" << sentence << '\n'; } else { bool found_word = false; for (size_t i = 2; i <= num.size(); ++i) { word_map::const_iterator entry = dict.find(num.substr(0, i)); if (entry != dict.end()) { found_word = true; for (unsigned j = 0; j < entry->second.size(); ++j) find_sentences(dict, rawnum, num.substr(i), sentence + " " + entry->second[j], false); } } if (!found_word && !trailing_digit) find_sentences(dict, rawnum, num.substr(1), sentence + " " + num[0], true); } } int main() { const word_map dict(read_words()); std::ifstream is("input.txt"); std::string raw_number; while (std::getline(is, raw_number)) find_sentences(dict, raw_number, filtered(raw_number), "", false); } // that's 49 non-blank, non-comment, non-just-curly-brace lines

index of blog posts