My Little Garden of Code

bloggings about codings

Some Notes on Building and Running Mirage Unikernels on Cubieboard2

| Comments

First a caveat: These notes reflect the state of Mirage as of the date of this post. Mirage is still in heavy development and the instructions here will change (hopefully become simpler) going forward.

These are some notes on what I had to do to get a Mirage unikernel running under Xen on a cubieboard2. The intent here is to document some of the gotchyas I ran into.

Installing Xen for ARM on Cubieboard

First download the pre-built img file from: http://blobs.openmirage.org/cubieboard2.tar

Extract the img file:

$ tar -xvf cubieboard2.tar

For the most part you can follow instructions here to copy the cubieboard2.img to a micro SD card, but I’ll add a little more detail here.

When you first plug in your empty micro SD card (I have a micro SD to USB adaptor) to your Linux computer you can discover which /dev it’s on by issuing:

$ fdisk -l

On my machine it showed up at /dev/sdb. Now use dd to copy the cubieboard2.img to the empty micrSD card:

$ dd if=cubieboard2.img of=/dev/sdb

After the copy is complete, plug the micro SD card into your Cubuieboard2 and boot it up. It will boot into Linaro Linux (14.04) on DOM0. If you have a USB to TTL serial cable (I got one from AdaFruit here: http://www.adafruit.com/products/954 ) you can plug that into your cubieboard2 (white to TX, green to RX, black to GND - don’t plug in the red wire to VCC). Connect the other side of the cable to your Linux machine and then you can watch the cubieboard boot up by running:

$ sudo screen /dev/ttyUSB0 115200

(NOTE: I’m running Fedora 20, not sure, but other distros may need a different device in place of /dev/ttyUSB0)

The cubieboard will get an address on your network using DHCP. Ater it finishes booting you can log in with username: mirage password: mirage and then run ifconfig to see what address has been assigned to it.

If you don’t have a USB to TTL serial cable you can check to see what address was assigned to the cubieboard by first (prior to powering up the cubieboard) issuing:

$  sudo arp-scan -I p4p1 192.168.1.0/16

(substitute your subnet for 192.168.1.0 if that isn’t the subnet of the network you’re on)

Note the devices attached to each address. Now power up your cubieboard, wait a couple of minutes and then reissue the arp command to see what new address has been added - the new address will be the address assigned by DHCP to your cubieboard.

Install mirage on the Cubieboard

Now that your cubieboard has booted you need to install mirage. Fortunately, the cubieboard2.img already comes with OCaml 4.01 and opam installed. Now install mirage:

$ opam init
$ opam install mirage-xen-minios
$ opam pin mirage https://github.com/talex5/mirage.git#link_c_stubs
$ opam pin mirage-xen https://github.com/mirage/mirage-platform
$ opam pin tcpip https://github.com/talex5/mirage-tcpip.git#checksum
$ opam install mirage    

Try out a Mirage example

I wanted to try out an example that uses networking on Xen which means that the OCaml TCPIP stack would be used. There are several examples in the mirage-skeleton repo: https://github.com/mirage/mirage-skeleton

Now ssh into your cubieboard and clone mirage-skeleton:

$ git clone git@github.com:philtomson/mirage-skeleton.git

(Notice that I’m pointing you to my mirage-skeleton repo, not the canonical one - I’ve made some changes to the stackv4 example config.ml so that you can easily specify DHCP which we’ll see a bit later, in the future, those changes will hopefully be in the main mirage-skeleton repo)

Now we’ll try out stackv4 which is a simple http server example.

$ cd mirage-skeleton/stackv4

Do the mirage configure, but set DHCP so that Mirage will create a main.ml file that uses DHCP instead of getting the hardcoded 10.0.0.2 (hardcoded in mirage):

$ DHCP=1 mirage configure --xen
$ mirage build

Now you will have run into a problem (at least as of this date, hopefully this will be fixed in the near future). You’ll see this error:

stackv4      ld: cannot find -lpthread
stackv4      ld: cannot find -lcrypto
stackv4      ld: cannot find -lssl
stackv4      make: build Error 1 

As it turns out, you don’t need those libraries, so edit the Makefile to remove the lines :

-lpthread \
-lcrypto \
-lssl \

Save the edited Makefile and run (again):

$ mirage build
$ make run

Notice the following message that comes from the make run:

stackv4.xl has been created. _Edit it to add VIFs_ or VBDs
Then do something similar to: xl create -c stackv4.xl

So now you need to edit the stackv4.xl, notice that it already has the following commented line:

# vif = [ 'mac=c0:ff:ee:c0:ff:ee,bridge=br0' ]

Edit it to remove the comment (#) and get rid of the mac address (I do not know if it is correct and since it possibly isn’t, and we don’t need it, best to just get rid of it. Make it look like:

vif = [ 'bridge=br0' ]

As an aside, where did the br0 come from? It’s possible you need something else there. Certainly I’ve seen other documents that had another identifier there. In order to figure out what it should be you should run:

$ brctl show

The result will be something like:

bridge name bridge id       STP enabled interfaces
br0     8000.02d908c0a687   no      eth0

The bridge name is what you’re going to want in the vif line above. In my case the comment matched the output of brctl so no change needed.

And now the moment we’ve been waiting for… start up that unikernel:

 sudo  xl create -c stackv4.xl   

If all went well, you should see that it reports the address it gets from DHCP:

 ...
 DHCP: offer received: 192.168.1.11
 ...
 DHCP: offer 192.168.1.11 255.255.255.0 [192.168.1.1]
  sg:true gso_tcpv4:true rx_copy:true rx_flip:false smart_poll:false
 ARP: sending gratuitous from 192.168.1.11
 DHCP offer received and bound
 Manager: configuration done
 IP address: 192.168.1.11

Now you can use curl on another machine on your network to see the hello world message:

$ curl http://192.168.1.11
hello mirage world!

And there you have it.

Shutting down the server

To shut down that mirage unikernel server on the cubieboard, issue the following:

$ sudo xl list
Name                                        ID   Mem VCPUs  State   Time(s)
Domain-0                                     0   512     2     r-----     194.3
stackv4                                     11   256     1     -b----       0.1

stackv4 is the one you want to stop (don’t stop Domain-0 as that’s the Linux instance running in DOM0 of Xen - the one you’re typing commands into)

$ sudo xl destroy stackv4

Cooperative Concurrency in OCaml: A Core.Std.Async Example

| Comments

I’ve been working on an OCaml Mqtt client for eventual use with MirageOS. Mqtt is a lightweight publish/subscribe messaging transport protocol that’s aimed at embedded systems and IoT applications. Without going into much detail about the protocol, implementing it requires some form of concurrency as there is a keep-alive ping that needs to be sent from the client to the broker at regular intervals to keep the connection alive. The client can also be receiving messages from the broker and needs to be able to queue up those messages for processing.

When considering concurrency options for OCaml, I thought I’d give Core.Std.Async (from here on, I’ll just refer to it as Async) a try as it’s covered in pretty good detail in chapter 18 of Real World OCaml. Of course, I didn’t see exactly what I needed in the examples there, so I had to play with a toy producer/consumer example for a bit. The code appears below, hopefully you’ll find it useful if you want to try out Async:

[] [title: producer_consumer.ml]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
(* compile with:
   corebuild -pkg async,unix  producer_consumer.native
*)
open Sys
open Async.Std
open Core

let (r,w) = Pipe.create ()

(* producer *)
let countup hi w =
  let rec loop i =
    printf "i=%d\n" i ;
    if (i < hi &&( not (Pipe.is_closed w))) then
       Pipe.write w i >>>
       fun () -> loop (i+1)
     else Pipe.close w
  in
  loop 0 ;;

(* consumer *)
let rec readloop r =
  Pipe.read r >>=
  function
  | `Eof -> return ()
  | `Ok v -> return (printf "Got %d\n" v) >>=
             fun () -> after (Time.Span.of_sec 0.5) >>=
             fun () -> readloop r  ;;


let () =
  Pipe.set_size_budget r 256  ;
  countup 10 w;
  ignore(readloop r);
  Core.Never_returns.never_returns (Scheduler.go ())

Async falls under the category of cooperative concurrency along with other frameworks that have an event loop like Python’s Twisted and Node.js. Preemptive concurrency is on the other side of the concurrency divide, and generally involves threads and mutexes. Cooperative concurrency is usually done by passing callbacks to functions that get called after some call in the function has returned data. Node.js is famous for this: you need to read data from some other website, for example, so you call your function for doing this and pass a callback to it that will actually return the data after it becomes available. Meanwhile instead of blocking waiting for the data to come back your program has gone on to call other functions in the event loop. This works fairly nicely (for some value of nicely) in Javascript where there are very few blocking calls… but note that callback hell is a thing as callbacks get nested into callbacks sometimes several layers deep.

Async works a bit differently, at least on the surface, from the asynchronous style of Javascript used in Node.js and this seems to help avoid the nested callback problem. Async is very monadic and that seems to help. Well-behaved Async functions don’t block, but instead return a value of type Deferred.t (Async.Deferred.t). A ‘a Deferred.t value is kind of like a promise in some other languages, a promise that the value you seek will be computed sometime in the future. There’s a scheduler that schedules these deferred events.

In addition, Async also has these very handy Pipe thingys that are basically FIFOs that connect different parts of your program together in a way that is reminiscent of Kahn Process Networks. (Async Pipes don’t have anything to do with Unix pipes other than a very surfacy resemblence)

You’ll notice that a Pipe is created at line 5 of the code above where r is the reader end of the pipe and w is the writer end. The countup function is our producer and simply counts up to a value passed in. On every iteration of the loop the new count value gets writen to the pipe at line 12 ( Pipe.write w i ). Notice that there’s an >>> operator at the end of that line. This is also called upon and could also have been written as: upon (Pipe.write w i) (fun () -> loop (i+1)). upon has the following type: ‘a Deferred.t -> (‘a -> unit) -> unit. When the deferred value that’s passed into upon is determined, the callback will be called, in this case we call loop (i+1) and recurse.

The readloop function (starting at line 19) uses the bind operator ( >>= ) which has the type: ‘a Deferred.t -> (‘a -> ‘b Deferred.t) -> ‘b Deferred.t. When the deferred value of Pipe.read r is determined, the result is passed into the callback function which will print what was received from the pipe (on success), then wait a half second before going on to call readloop again. For more details about the sequencing operators >>= (bind), >>> (upon) and >>| (map) have a look at the Real World OCaml link above. Notice that we use return to wrap a value in a Deferred.t (the type of return is ‘a -> ‘a Deferred.t) in order to make readloop type-check and compile as readloop’s type is: int Pipe.Reader.t -> unit Deferred.t.

So countup writes values to the Pipe while readloop reads values from it at half second intervals. If you compile this program and run it you’ll see:

i=0
i=1
Got 0
i=2
i=3
i=4
i=5
i=6
i=7
i=8
i=9
i=10
Got 1
Got 2
Got 3
Got 4
Got 5
Got 6
Got 7
Got 8
Got 9

The first lines up until ‘i=10’ come out pretty much instantaneously, while the next lines (‘Got 1’ through ‘Got 9’) came out every half second.

However… Notice line 32 of the code above: Pipe.set_size_budget r 256 ; Initially I thought (based on the explanation in RWO) that Pipes were queues of infinite length. I didn’t know you had to set_size_budget on the Pipe. So earlier attempts omitted line 32 above and I got the following result:

i=0
i=1
Got 0
i=2
Got 1
i=3
Got 2
i=4
Got 3
i=5
Got 4
i=6
Got 5
i=7
Got 6
i=8
Got 7
i=9
Got 8
i=10
Got 9

(With a half second delay between each ‘Got’ message)

The Pipe.write seemed to block waiting for a Pipe.read which didn’t seem right given the description of Pipe in RWO. But as it turns out the pipe size defaults to 0 which means that the pipe fills up immediately. To get a deeper pipe, you need to call set_budget_size on the pipe (either end, apparently) as shown on line 32 of the code above. (Aside: It seems like there should be an optional parameter budget_size to the Pipe.create function.)

Conclusions

While in essense we’re still using callbacks in our event loop (very Javascript/Node.js-ish), the monadic sequencing operators >>=, >>| and >>> do seem to make the code easier to read and reason about. Add in the handy Pipes and it’s not a bad way to do concurrency, really, once you get the hang of dealing with the monads. It should be noted, however, that as in most cooperative concurrency schemes, you’re only going to be using one core of your processor.

Finally… I’m pretty new to Core and Async so if I’ve made some mistakes here in the explanation or if the code could be more elegant please don’t hesitate to let me know in the comments.

Stop the Presses: OCaml Wins in Terms of Speed

| Comments

Benchmarking is a tricky thing.

Several sharp eyes noticed some flaws in the OCaml code in my last post.

The main problem was pointed out by Kim Nguyễn in the comments:

your OCaml version is flawed… First in F# you do every computation in integer and only convert as float at the end (it seems). If you do the same in OCaml, you will gain some speed, that is: list_sum should use 0 and +, and distance should use let x = a - b in x*x to compute the square and only call “float” before sqrt, as you do in F# (and therefore also call float at the end on num_correct since list_sum now returns an integer. Also the computation of num_correct should use now 1 and 0 instead of 1.0 and 0.0).

I made the suggested changes to distance and list_sum :

[] [title: integer math in distance and list_sum]
1
2
3
4
5
let list_sum lst = List.fold_left (fun x acc -> x+acc) 0 lst

let distance (p1: int list) (p2: int list) =
  sqrt (float_of_int (list_sum (List.map2 ( fun a b -> let diff = a-b in
                                           diff*diff ) p1 p2) ))

Those simple changes yielded a 2X speedup which puts the OCaml implementation on par with the non-parallelized F# version:

real    0m23.874s
user    0m23.623s
sys         0m0.079s

Then camlspotter pointed out something about float array that I’d forgotten:

In addition, comparing programs using Arrays and Lists is VERY unfair. In this kind of programs with loops you cannot ignore the cost of list construction and deconstruction. In addition, OCaml’s float array has another benefits: its contents are unboxed, while float list does not.

camlspotter was kind enough to submit an Arrayized version of the OCaml code:

[] [title: classifyDigitsArray.ml]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
(* OCaml version submitted by @camlspotter
   compile with:
    ocamlopt str.cmxa -o classifyDigitsArray classifyDigitsArray.ml 
*)

(*
// This F# dojo is directly inspired by the 
// Digit Recognizer competition from Kaggle.com:
// http://www.kaggle.com/c/digit-recognizer
// The datasets below are simply shorter versions of
// the training dataset from Kaggle.
 
// The goal of the dojo will be to
// create a classifier that uses training data
// to recognize hand-written digits, and
// evaluate the quality of our classifier
// by looking at predictions on the validation data.
 
*)

let read_lines name : string list =
  let ic = open_in name in
  let try_read () =
    try Some (input_line ic) with End_of_file -> None in
  let rec loop acc = match try_read () with
    | Some s -> loop (s :: acc)
    | None -> close_in ic; List.rev acc in
  loop []

(*
 
// Two data files are included in the same place you
// found this script: 
// trainingsample.csv, a file that contains 5,000 examples, and 
// validationsample.csv, a file that contains 500 examples.
// The first file will be used to train your model, and the
// second one to validate the quality of the model.
 
// 1. GETTING SOME DATA
 
// First let's read the contents of "trainingsample.csv"
 
*)

type labelPixels = { label: int; pixels: int array }
let slurp_file file =
  List.tl (read_lines file)
  |> List.map (fun line -> Str.split (Str.regexp ",") line )
  |> List.map (fun numline -> List.map (fun (x:string) -> int_of_string x) numline)
  |> List.map (fun line ->
    { label= List.hd line;
      pixels= Array.of_list @@ List.tl line })
  |> Array.of_list

let trainingset = slurp_file "./trainingsample.csv"

(* 
// 6. COMPUTING DISTANCES
 
// We need to compute the distance between images
// Math reminder: the euclidean distance is
// distance [ x1; y1; z1 ] [ x2; y2; z2 ] = 
// sqrt((x1-x2)*(x1-x2) + (y1-y2)*(y1-y2) + (z1-z2)*(z1-z2))
*)

let array_fold_left2 f acc a1 a2 =
  let open Array in
  let len = length a1 in
  let rec iter acc i =
    if i = len then acc
    else
      let v1 = unsafe_get a1 i in
      let v2 = unsafe_get a2 i in
      iter (f acc v1 v2) (i+1)
  in
  iter acc 0

let distance p1 p2 =
  sqrt
  @@ float_of_int
  @@ array_fold_left2 (fun acc a b -> let d = a - b in acc + d * d) 0 p1 p2

(* 
// 7. WRITING THE CLASSIFIER FUNCTION
 
// We are now ready to write a classifier function!
// The classifier should take a set of pixels
// (an array of ints) as an input, search for the
// closest example in our sample, and predict
// the value of that closest element.
 
*)

let classify (pixels: int array) =
  fst (
    Array.fold_left (fun ((min_label, min_dist) as min) (x : labelPixels) ->
      let dist = distance pixels x.pixels in
      if dist < min_dist then (x.label, dist) else min)
      (max_int, max_float) (* a tiny hack *)
      trainingset
  )

(*
// 8. EVALUATING THE MODEL AGAINST VALIDATION DATA
 
// Now that we have a classifier, we need to check
// how good it is. 
// This is where the 2nd file, validationsample.csv,
// comes in handy. 
// For each Example in the 2nd file,
// we know what the true Label is, so we can compare
// that value with what the classifier says.
// You could now check for each 500 example in that file
// whether your classifier returns the correct answer,
// and compute the % correctly predicted.
*)

let validationsample = slurp_file "./validationsample.csv"

let num_correct =
  Array.fold_left (fun sum p -> sum + if classify p.pixels = p.label then 1 else 0) 0 validationsample

let _ =
  Printf.printf "Percentage correct:%f\n"
  @@ float_of_int num_correct /. float_of_int (Array.length validationsample) *.100.0

Now the non-parallelized OCaml version handily beats the parallelized F# version(by about 5 seconds):

real    0m11.686s
user    0m11.529s
sys     0m0.092s

…though the code is a good bit longer than the F# version which weighed in at 58 lines.

Observations:

  1. Be very careful about where you’re doing integer vs float math ops; stay with ints as much as possible (so long as you’re not sacrificing accuracy).
  2. float array is preferrable to float list because the floats are unboxed in the former.
  3. Don’t be obsessed with making an implementation in one language look like the implementation in the comparison language. I think I was focusing too much on the similiarities of the languages to see some of the optimization opportunities. Also, since I wrote the F# version first, I tended to make the OCaml version look like the F# version (usage of minBy, for example, and implementing my own minBy in OCaml instead of using camlspotter’s Array.fold_left method.)
  4. The parallelization point remains: It’s much easier in F#. How fast would this be if OCaml’s Parmap used some kind of shared-memory implementation? The F# example was about 1.4X faster with Parallel so that would get the OCaml version down to ~8.5 seconds if a similar mechanism existed.

Comparing a Machine Learning Algorithm Implemented in F# and OCaml

| Comments

(UPDATE: please see the next post: Stop the Presses: OCaml wins in terms of speed in which it is shown that there were some serious flaws in my OCaml implementation below. I’ll keep this post around for reference.)

I’ve been dabbling with OCaml for the last several years and so when I saw a recent Meetup notice about an F# machine learning code dojo being led by Mathias Brandewinder within walking distance of my house I thought I’d check it out. I’m one of those Linux guys who tends to eschew IDEs, prefers to use vim, and considers .NET to be some very foreign territory. F# is based on OCaml, so I figured I’d have a bit of a headstart in the language area even if I haven’t done any .NET development.

Also, I was curious as I had been hearing rumors on twitter that F# programs were running on Mono faster than the equivalent OCaml versions. I was also taking Andrew Ng’s Coursera Machine Learning course so the timing seemed good. So I loaded up mono, monodevelop and F#. As it turns out none of it worked on the day of the dojo, so I looked on with someone with a Windows laptop and Visual Studio.

The code dojo itself was a great way of learning F#. Check out Mathias’ Digits Recognizer code Dojo code and instructions which in turn was based on a Kaggle Machine Learning challenge. The task was to implement a k-NN (K Nearest Neighbor; in this case K=1) algorithm for recognizing handwritten digits from a dataset that was provided: A training set of 5000 labeled examples and a validation set of 500 labeled examples. Each digit example is a set of 28X28 grayscale pixels (784 integer values from 0 to 255). We wrote a classifier that reads in the training set and then compares each of the 500 validation samples against those 5000 training exmples and returns the label associated with the closest match (the vector with the shortest distance from a training example). k-NN is one of the simplest machine learning algorithms, even so, we were able to get a 94.4% accuracy rate.

After the Dojo, I spent some time getting Monodevelop and F# running on my Ubuntu 12.04 laptop. Turns out I needed to get Monodevelop 4.0 (built from source) and F# 3.0 (initially tried F# 3.1, but Monodevelop 4.0 wasn’t happy with that version). Then I set about reimplementing the algorithm in F# and after I got that working I reimplemented the same algorithm in OCaml.

Here’s my F# implementation:

[] [title: ClassifyDigits.fs]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
module classifyDigits.Main

open System
open System.IO

type LabelPixels = { Label: int; Pixels: int[] }
let slurp_file file =
   File.ReadAllLines(file).[1..]
   |> Array.map (fun line -> line.Split(','))
   |> Array.map (fun numline -> Array.map (fun (x:string) -> Convert.ToInt32(x)) numline)
   |> Array.map (fun line -> { Label= line.[0]; Pixels=line.[1..] })

//load the trainingsample  
let trainingset = slurp_file("/home/phil/devel/f_sharp/Dojo-Digits-Recognizer/Dojo/trainingsample.csv")

//  COMPUTING DISTANCES

// We need to compute the distance between images
// Math reminder: the euclidean distance is
// distance [ x1; y1; z1 ] [ x2; y2; z2 ] = 
// sqrt((x1-x2)*(x1-x2) + (y1-y2)*(y1-y2) + (z1-z2)*(z1-z2))

let distance (p1: int[]) (p2: int[]) =
  Math.Sqrt (float(Array.sum (Array.map2 ( fun a b -> (pown (a-b) 2)) p1 p2) ))


//  WRITING THE CLASSIFIER FUNCTION

// We are now ready to write a classifier function!
// The classifier should take a set of pixels
// (an array of ints) as an input, search for the
// closest example in our sample, and predict
// the value of that closest element.

let classify (pixels: int[]) =
  fst (trainingset |> Array.map (fun x -> (x.Label, (distance pixels x.Pixels ) ))
                   |> Array.minBy (fun x -> snd x ))

// EVALUATING THE MODEL AGAINST VALIDATION DATA

// Now that we have a classifier, we need to check
// how good it is. 
// This is where the 2nd file, validationsample.csv,
// comes in handy. 
// For each Example in the 2nd file,
// we know what the true Label is, so we can compare
// that value with what the classifier says.
// You could now check for each 500 example in that file
// whether your classifier returns the correct answer,
// and compute the % correctly predicted.


let _ =
    Console.WriteLine("start...")
    let validationsample = slurp_file("/home/phil/devel/f_sharp/Dojo-Digits-Recognizer/Dojo/validationsample.csv")
    let num_correct = (validationsample |> Array.map (fun p -> if (classify p.Pixels ) = p.Label then 1 else 0)
                                        |> Array.sum)
    Printf.printf "Percentage correct:%f\n" ((float(num_correct)/ (float(Array.length validationsample)))*100.0)

Timing when running this on my Dell XPS 13 (i7 Haswell, 8GB RAM):

real        0m22.180s
user        0m22.253s
sys         0m0.116s

And the OCaml implementation:

[] [title: classifyDigits.ml]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
(* OCaml version
   compile with:
    ocamlopt str.cmxa -o classifyDigits classifyDigits.ml 
*)

let read_lines name : string list =
  let ic = open_in name in
  let try_read () =
    try Some (input_line ic) with End_of_file -> None in
  let rec loop acc = match try_read () with
    | Some s -> loop (s :: acc)
    | None -> close_in ic; List.rev acc in
  loop []

type labelPixels = { label: int; pixels: int list }
let slurp_file file =
   List.tl (read_lines file)
   |> List.map (fun line -> Str.split (Str.regexp ",") line )
   |> List.map (fun numline -> List.map (fun (x:string) -> int_of_string x) numline)
   |> List.map (fun line -> { label= (List.hd line); pixels=(List.tl line) })

let trainingset = slurp_file("./trainingsample.csv")

(* 
// COMPUTING DISTANCES
 
// We need to compute the distance between images
// Math reminder: the euclidean distance is
// distance [ x1; y1; z1 ] [ x2; y2; z2 ] = 
// sqrt((x1-x2)*(x1-x2) + (y1-y2)*(y1-y2) + (z1-z2)*(z1-z2))
*)

let list_sum lst = List.fold_left (fun x acc -> x+.acc) 0.0 lst

let distance (p1: int list) (p2: int list) =
  sqrt (list_sum (List.map2 ( fun a b -> (float_of_int(a-b)**2.0)) p1 p2) )

(* 
// WRITING THE CLASSIFIER FUNCTION
 
// We are now ready to write a classifier function!
// The classifier should take a set of pixels
// (an array of ints) as an input, search for the
// closest example in our sample, and predict
// the value of that closest element.
*)

let minBy f lst  =
  let smallest = ref (List.hd lst) in
  List.iter (fun x -> if (f x) < (f !smallest) then smallest := x
                          ) (List.tl lst) ;
  !smallest ;;


let classify (pixels: int list) =
  fst ((List.map (fun (x: labelPixels) -> (x.label, (distance pixels x.pixels) )) trainingset)
       |> minBy (fun x  -> snd x)  )

(*
// EVALUATING THE MODEL AGAINST VALIDATION DATA
 
// Now that we have a classifier, we need to check
// how good it is. 
// This is where the 2nd file, validationsample.csv,
// comes in handy. 
// For each Example in the 2nd file,
// we know what the true Label is, so we can compare
// that value with what the classifier says.
// You could now check for each 500 example in that file
// whether your classifier returns the correct answer,
// and compute the % correctly predicted.
*)

let validationsample = slurp_file("./validationsample.csv")
let num_correct = (validationsample |> List.map (fun p -> if (classify p.pixels ) = p.label then 1. else 0.) |> list_sum)
let _ = Printf.printf "Percentage correct:%f\n" (((num_correct)/. (float_of_int(List.length validationsample)))*.100.0)

The code is very similar. The OCaml version is a bit longer because I needed to implement some functions that are built into the F# library, specifically, minBy (Array.minBy is built in to thd F# standard lib), list_sum (Array.sum is the F# builtin function) and read_lines (File.ReadAllLines is the F# builtin). One difference that could possibly effect performance: The F# version reads the data into Arrays whereas the OCaml version reads the data into Lists. The OCaml version was just easier to read into a List and OCaml’s List module has a map2 function whereas OCaml’s Array module does not (F# apparently has a map2 for both Array and List).

(EDIT: But as it turns out, using a List here instead of an Array is probably responsible for about 1/2 of the performance difference between the F# and the OCaml version. See the update )

I was surprised how much less performant the OCaml version was:

real    0m47.311s
user    0m46.881s
sys     0m0.135s

The F# implementation was slightly more than twice as fast o_O.

Next, I recalled from the dojo that it’s very easy to parallelize the maps in F#; instead of Array.map you use Array.parallel.map. So after a couple of edits to add parallel maps, I rebuilt and ran with the following time:

real    0m16.400s
user    0m47.135s
sys     0m0.240s

So after that very simple change the F# version was very nearly 3X faster than the OCaml version. And in top I could see that the CPU usage was up to 360% as it ran.

Ah, but what about OCaml’s Parmap? I modified my OCaml version to use Parmap… but it took a lot longer to get it working than parallelizing the F# version. Probably about 30 minutes by the time I got it figured out (including figuring out how to compile it).

Here’s the OCaml version of the classify function and num_correct that uses Parmap:

[] [title: classifyDigitsPar.ml]
1
2
3
4
5
6
7
let classify (pixels: int list) =
  let label_dist = Parmap.parmap ~chunksize:50 ~ncores:4 (fun x -> (x.label, (distance pixels x.pixels) )) (Parmap.L trainingset) in
  let min = minBy (fun x y -> compare (snd x) (snd y)) label_dist in
  fst min

let num_correct =
  (Parmap.L validationsample) |> Parmap.parmap ~ncores:4 (fun p -> if (classify p.pixels ) = p.label then 1. else 0.) |> list_sum

Notice that you have to tell it how many cores you have.

After I got it to compile I ran it with much anticipation…

real    1m43.140s
user    5m38.809s
sys     0m42.811s

… over twice as slow as the original OCaml implementation. I noticed in top that this version launched 4 different classifyDigitPar processes so I’m guessing that it uses sockets to communicate between the processes. For this particular problem that doesn’t appear to be effective. Perhaps it would be for a longer running example, but I’m not sure. F# certainly wins in the parallelization department.

Observations

Other than performance (where F# on Mono seems to win handily) I noticed the following:

  1. The Array slicing syntax in F# is quite nice.
  2. F#’s standard library is just more comprehensive. I could have probably used Janestreet’s Core library for OCaml which is quite comprehensive, but I wanted to stick with the standard library for both.
  3. Monodevelop has a vi editing mode. It’s kind of ok. But it’s missing a lot of keybindings that you’d have in native vi.
  4. I have no idea what F#’s (or Monodevelop’s) equavilent to opam is. I’m guessing OCaml wins in the package management department.
  5. F#’s polymorphic math operators were nice (no need for +., etc.).

You can find the code above in my github

Next Time

I want to implement the algorithm in Julia. I’m going to guess that Julia’s vectorization support means that it will beat both OCaml and F#.

Drawing Happy Little Trees: Tree Meditation #2

| Comments

Alt Ash Tree

In the previous Tree Meditation we pondered some preliminary ideas about treeness. Now let’s think about how to draw our trees. Before we start, make sure you paste this tree type code from the last installment into the Try OCaml REPL:

[] [title: our tree type definition]
1
type 'a tree = Empty | Leaf of 'a | Node of 'a tree * 'a * 'a tree

Last time we coded our little tree using the constructors Empty, Leaf, and Node defined in our tree type:

[] [title: Our first happy little tree ]
1
2
Node(Leaf 2, 1, Leaf 3) ;;
- : int tree = Node (Leaf 2, 1, Leaf 3)

NOTE: if you’re using your own local OCaml REPL (ocaml or utop) make sure you terminate all of the entries here with double semicolon: ;; The Try Ocaml REPL seems to do this for you automatically.

To create a picture of the tree we’ll use Graphviz which is a suite of commandline tools that can be used to visualize graphs. Since our tree is a graph, we can use Graphviz to visualize it. Specifically, we’ll use a program called dot to create a visual representation of the graph.

This is what our tree should look like in the dot language:

[] [title: tree.dot ]
1
2
3
4
  graph tree {
    {N1[label="1"]}-- {L2[shape=box,label="2"]}
    {N1[label="1"]}-- {L3[shape=box,label="3"]}
  }

We have a graph called tree. Inside of the tree block we define the connections between the nodes (or in our case between Nodes and/or Leafs, but no Emptys, of course, as they’re invisible).

Each node in the graph needs a unique identifier which is what N1,L2 and L3 are above. We also give each node a label which is what is shown in the graphical output of the tree. That’s the [label=”some label”] part of the node specifications above.

The ‘–’ means that there is a connection between two nodes.

It’s a fairly simple representation of our tree. We can generate the picture of the tree by running:

$ dot -Tsvg -o happy_tree.svg tree.dot

This will generate the file happy_tree.svg which we see here:

Alt Our Happy Tree

That’s nice and all, but what if our tree is much larger than this one and has many nodes and leaves? We’d like to be able to generate the tree.dot file automatically from our coded representation of our tree. To do that we need to talk a bit about tree traversal (visiting each node or leaf of our tree structure).

Let’s create a somewhat bigger tree to make our traversal discussion clearer:

[] [title: bigger tree ]
1
2
3
4
5
6
7
8
9
10
11
12
let t = Node (
              Node (
                    Leaf "0",
                    "1",
                    Leaf "2"),
              "3",
              Node (
                    Leaf "4",
                    "5",
                    Leaf "6"
              )
         )

Which looks like:

Alt Our Happy Tree

So why the odd order of the numbers in the tree above? One thing that’s not clear in our type definition from the previous article is that, by convention, an important property of binary trees is that child trees to the left of the current node should contain values that are less than the value held in the current node and child trees to the right of the current node should contain values that are greater than the value of the current node.

(As an aside, if we wanted to encode that requirement in our type definition we would need to be using a language which has dependent types )

Our chosen ordering above will become clearer as we talk about different types of traversal.

Tree Traversal

In order to generate a dot file that represents our tree we’ll need to traverse the nodes of our tree meaning we need to somehow visit all of the nodes of our tree structure.

There are two categories of tree traversal: Depth First or Breadth First (aka Level Order Traversal).

In all cases we start the tree traversal from the root of the tree. In our tree above, the root of the tree is the node that contains the value 3. (For whatever reason, in Computer Science trees are generally upside-down with the root at the top and the leaves at the bottom.)

Depth First Traversal

There are three ways to do a depth-first traversal of a tree:

1. Pre-order Traversal

The steps of a Pre-order traversal:

  1. Visit the current node and do something with the value found there.
  2. Traverse the left subtree.
  3. Traverse the right subtree.

An OCaml function to do a preorder traversal is defined as follows:

[] [title: preorder tree traversal function]
1
2
3
4
5
6
let rec preorder_traverse t = match t with
  | Empty           -> ()
  | Leaf  value     -> Printf.printf "%s " value
  | Node (l,value,r)-> Printf.printf "%s " value;
                       preorder_traverse l;
                       preorder_traverse r

The recursive preorder_traverse function (note the rec in the function definition) takes a tree and uses pattern matching to determine what to do with each variant in the tree type. If t is an Empty we do nothing (empty parens () also known as unit in OCaml) . If It’s a Leaf we print it’s value. If it’s a Node we print it’s value and then call preorder_traverse on the left tree of the node and then call preorder_traverse on the right tree of the node.

Running this on our tree above we get (You’ve been typing the code into the online OCaml REPL right?) :

# preorder_traverse t ;;
3 1 0 2 5 4 6 - : unit = ()

2. In-order Traversal

The steps of an In-order traversal:

  1. Traverse the left subtree.
  2. Visit current node and do something with value found there.
  3. Traverse the right subtree.

Here’s the OCaml function for an inorder traversal:

[] [title: inorder tree traversal function]
1
2
3
4
5
6
let rec inorder_traverse t = match t with
  |  Empty            -> ()
  |  Leaf value       -> Printf.printf "%s " value
  |  Node (l,value,r) -> inorder_traverse l ;
                         Printf.printf  "%s " value;
                         inorder_traverse r

Running this on our tree we get:

# inorder_traverse t ;;
0 1 2 3 4 5 6 - : unit = ()

Now you can get an idea of why we arranged the values in our tree as we did.

3. Post-order Traversal

Now you probably get the idea. For postorder we’re going to traverse the left subtree then traverse the right subtree and finally visit the current node and do something with it’s value:

[] [title: inorder tree traversal function]
1
2
3
4
5
6
let rec postorder_traverse t = match t with
  |  Empty  -> ()
  |  Leaf value -> Printf.printf "%s " value
  |  Node (l,value,r) ->  postorder_traverse l;
                          postorder_traverse r;
                          Printf.printf  "%s " value

And when we run this on our tree we get:

# postorder_traverse t ;;
0 2 1 4 6 5 3 - : unit = ()

As an aside, instead of just printing the current value we’d probably want to make each of our traversal functions more general. This is functional programming, after all, and one of the great “wins” of functional programming is being able to pass functions to functions - function composition. We can generalize our traversal functions by passing in a function that will do something with the value:

[] [title: generalized inorder tree traversal function]
1
2
3
4
5
6
let rec postorder_traverse f t = match t with
  |  Empty            -> ()
  |  Leaf value       -> f value
  |  Node (l,value,r) -> postorder_traverse f l;
                         postorder_traverse f r;
                         f value

Then we could use this version of postorder_traverse to print the values in our tree:

# postorder_traverse (fun n -> Printf.printf "%s " n) t;;
0 2 1 4 6 5 3 - : unit = ()

Notice that none of these depth first traversals of the tree will work for us in creating the dot file for graphviz. We need some other way to traverse the tree…

We need something that gives us (not actual dot code, but you get the idea):

3 -> 1
3 -> 5
1 -> 0
1 -> 2
5 -> 4
5 -> 6

Which brings us to…

Breadth First (or Level Order) Traversal

A Level Order traversal means we’re traversing each level of the tree. A Level order traversal of our tree above would look like(line breaks added to emphasize the levels of the tree):

3 
1 5 
0 2 4 6

This still isn’t quite what we need yet, but it seems we’re getting closer.

Before we go on, let’s define a couple of helper functions that we’ll need to construct our dot file.

First off, we’ll need to construct a string that gets written to the dot file. It would be good to have a function that converts each of the 3 variants that can make up a tree type to a string in dot format that represents the node in the graph:

[] [title: to_dot_node]
1
2
3
4
let to_dot_node (t: 'a tree) : string = match t with
  | Empty -> ""
  | Node(_,x,_) -> "{N"^x^"[label=\"" ^x^"\"]}"
  | Leaf x ->      "{L"^x^"[shape=box,label=\"" ^x^ "\"]}"

Notice that in this function definition we explicitly specified that the t argument passed to this function should be of type ‘a tree and the output is of type string - this is completely optional as the compiler can figure out the types of the arguments using type inference, but it can make the code easier to read. (Note: ^ is the string concatenation operator in OCaml)

If you pasted that function in the REPL you’ll see:

val to_dot_node : string tree -> string = <fun> 

Which means that this is a function that takes a string tree and returns a string.

We can try running this function on our tree:

# to_dot_node t ;;
- : string = "{N3[label=\"3\"]}"

Which is the label of the root of our tree (3).

Next, we’ll define a function that given two inputs of type ‘a tree will return an edge (a line between two nodes in the tree) in dot format:

[] [title: edge]
1
let edge (n1: 'a tree ) (n2 : 'a tree ) : string = (to_dot_node n1)^"--"^(to_dot_node n2)^"\n"

Now we can go on to define our tree_to_dot function:

[] [title: tree_to_dot]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
let rec tree_to_dot  acc t =
  match t with
  | Empty -> acc
  | Leaf _ as leaf ->   acc ^ (to_dot_node leaf)
  | Node( (Node (_,_,_) as n) , _,  (Leaf _ as leaf))
  | Node( Leaf _ as leaf, _, (Node (_,_,_) as n))     ->
      (edge t n) ^ (edge t leaf) ^(tree_to_dot acc n)
  | Node( ( Node(_,_,_)  as n) , _,  Empty)
  | Node( Empty, _, (Node(_,_,_) as n))    ->
      (edge t n) ^ (tree_to_dot acc n)
  | Node( ( Leaf _  as leaf), _, Empty)
  | Node( Empty, _,(Leaf _ as leaf))   ->
      (edge t leaf)
  | Node( (Leaf _ as left), _, (Leaf _ as right)) ->
      (edge t left) ^ (edge t right)
  | Node( Empty, _, Empty) ->
      acc
  | Node( (Node (_,_,_) as nl) , _, (Node(_,_,_) as nr)) ->
      (edge t nl)^(edge t nr)^(tree_to_dot acc nl)^(tree_to_dot acc nr)

The first argument to tree_to_dot is acc which is specified as being a string. acc is our accumulator: we’ll use it to build up our dot file. Notice that the function is specified as being recursive ( the rec specifies that the function can call itself).

Our pattern match covers all of the potential cases we might encounter. The first one matches t with Empty and in that case returns our accumulator acc. The next match is against Leaf _ (underscore there meaning that the Leaf could contain any value). If t is a Leaf, then we’ll append the Leaf’s dot node format to the accumulator.

After this we do several matches where t is a Node variant. In order to create an edge we need to know about the children of the current Node. Pattern Matching allows us to do this, the first pattern match against Node is:

  | Node( (Node (_,_,_) as n) , _,  (Leaf _ as leaf))
  | Node( Leaf _ as leaf, _, (Node (_,_,_) as n))     ->
      (edge t n) ^ (edge t leaf) ^(tree_to_dot acc n)

We’re considering two cases here:

  1. The case where the Node contains a Node as the left sub-tree and a Leaf in the right sub-tree.
  2. The case where the Node contains a Leaf as the left sub-tree and a Node in the right sub-tree.

If either of these cases match, we then create an edge from the current Node (which is t) to the next Node (which is n) and an edge from the current Node (t) to the Leaf (leaf). And we concatenate that with the recursive call to tree_to_dot acc n, meaning we’re passing the child node n on to tree_to_dot for further processing.

Next we match the two cases where there’s a single child Node and a single Empty node. If so we create an edge from the current Node (t) to the child Node and concatenat that with the call to tree_to_dot given the child Node n.

After that we match the two cases where one child of the Node is a Leaf and the other is Empty. If these cases match we only return an edge from the current Node t to the child Leaf. No recursive call to tree_to_dot in this case. Since there are no child Nodes, there’s no reason to.

If both sub-trees of the current Node t are Leafs then the next pattern matches and we concatenate the two edges from the current Node t to each Leaf.

In the next case we check for both sub-trees of the Node being Empty and if that case matches we just return the accumulator.

Finally, we cover the case where both sub-trees of the current node are Nodes. Notice that if this case matches we have two calls to tree_to_dot - one for the left subtree and the other for the right subtree.

Now we just need to do a bit of housekeeping to write out the complete dot file:

[] [title: tree_to_dotfile]
1
2
3
4
5
let tree_to_dotfile t file =
  let dot_tree = "graph tree {\n"^(tree_to_dot " " t)^"}" in
  let channel = open_out file in
  output_string channel dot_tree;
  close_out channel

This function won’t work in the Try OCaml REPL since it writes to a file. But maybe by now you’ve been convinced to install OCaml. If so, here’s the whole program so you can compile it:

[] [title: tree.ml]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
type 'a tree = Empty | Leaf of 'a | Node of 'a tree * 'a * 'a tree

let to_dot_node (t: 'a tree) : string = match t with
  | Empty -> ""
  | Node(_,x,_) -> "{N"^x^"[label=\"" ^x^"\"]}"
  | Leaf x ->      "{L"^x^"[shape=box,label=\"" ^x^ "\"]}"

let edge (n1: 'a tree ) (n2 : 'a tree ) : string = (to_dot_node n1)^"--"^(to_dot_node n2)^"\n"

let rec tree_to_dot (acc : string) (t : 'a tree) : string =
  match t with
  | Empty -> acc
  | Leaf _ as leaf ->   acc ^ (to_dot_node leaf)
  | Node( (Node (_,_,_) as n) , _,  (Leaf _ as leaf))
  | Node( Leaf _ as leaf, _, (Node (_,_,_) as n))     ->
      (edge t n) ^ (edge t leaf) ^(tree_to_dot acc n)
  | Node( ( Node(_,_,_)  as n) , _,  Empty)
  | Node( Empty, _, (Node(_,_,_) as n))    ->
      (edge t n) ^ (tree_to_dot acc n)
  | Node( ( Leaf _  as leaf), _, Empty)
  | Node( Empty, _,(Leaf _ as leaf))   ->
      (edge t leaf)
  | Node( (Leaf _ as left), _, (Leaf _ as right)) ->
      (edge t left) ^ (edge t right)
  | Node( Empty, _, Empty) ->
      acc
  | Node( (Node (_,_,_) as nl) , _, (Node(_,_,_) as nr)) ->
      (edge t nl)^(edge t nr)^(tree_to_dot acc nl)^(tree_to_dot acc nr)

let tree_to_dotfile t file =
  let dot_tree = "graph tree {\n"^(tree_to_dot " " t)^"}" in
  let channel = open_out file in
  output_string channel dot_tree;
  close_out channel;;

let t = Node (
              Node (
                    Leaf "0",
                    "1",
                    Leaf "2"),
              "3",
              Node (
                    Leaf "4",
                    "5",
                    Leaf "6"
              )
         )



let _ = tree_to_dotfile t "tree.dot"

You can compile it with the following command:

$ ocamlopt -o tree tree.ml

That’s all there is to it

Coding Happy Little Trees: Tree Meditation #1

| Comments

Alt Bob Ross

It all started a few months ago when I created a quad-tree structure and then wanted to be able to visualize those trees with GraphViz. Thus this tree meditation was born. And who was the master of happy little trees? Bob Ross of course. So if you like, read the following in Bob’s very relaxing voice…. try not to go to sleep.

Before we can code our happy little trees we need to define what a tree is:

[] [title: binary tree type in OCaml]
1
# type 'a tree = Empty | Leaf of 'a | Node of 'a tree * 'a * 'a tree ;;

You can go ahead and type that yourself into the online OCaml REPL (Read Evaluate Print Loop). Go ahead, give it a try.

The type definition here is in OCaml. The ML family of languages (SML, OCaml and Haskell, for example) excel at creating pretty trees because they have algebraic data types. What’s the ‘a tree mean? The ‘a is a type variable and means that we’re creating trees which contain data of type ‘a. Since ‘a isn’t specified it means that any type of data could live in the tree; our tree is polymorphic.

Since this is a SUM type (also called an OR type, notice the ‘|’s in the definition above) we can surmise that a tree can either be Empty or have a Leaf or a Node. Empty, Leaf and Node are used to build our tree, they are our tree constructors.

Empty, what’s that mean? Think of it as the tree of nothingness. Very Zen. Hopefully it will make more sense when we start creating and traversing trees.

Leaf of ‘a means that a leaf can contain data of type ‘a and as was explained above, that means that the leaf can contain data of any type. How do we create a Leaf of ‘a in our code?

[] [title: How to make a leaf]
1
2
# Leaf "I'm a Leaf" ;;
- : string tree = Leaf "I'm a Leaf"

The above was typed into the OCaml REPL. The # is the REPL prompt, we only typed in the actual Leaf “I’m a Leaf” part. The second line shows the result. Notce that the type is string tree because we passed a string to the Leaf constructor. So our leaf is itself a tree. Ok, maybe that seems a little stange, but hold up a leaf by the stem and it can certainly look like a little tree on it’s own, don’t you think? Fractals, think fractals.

Now we’re left with that Node of ‘a tree * ‘a * ‘a tree part of the tree type definition. Here we’ve reached the essence of treeness. A Node of a tree has three parts: A ‘a tree on the left, the actual ‘a data contained by this Node and another ‘a tree on the right. This part of the definition of tree is recursive because a Node is the piece of a tree which can contain other trees - in our case we have defined a binary tree type since each node has only two branches: a left tree and a right tree. What’s with the asterisks? Technically they indicate that this part of the type is a Cartesian product (algebraic datatypes remember). We can think of this particular one as a triple - a collection of 3 things.

So without further ado, let’s code a happy little tree:

[] [title: Our first happy little tree ]
1
2
# Node(Leaf 2, 1, Leaf 3) ;;
- : int tree = Node (Leaf 2, 1, Leaf 3)

The REPL tells us this is an int tree, a tree which contains integers at it’s nodes and leaves.

And what does it look like?

Alt Our Happy Tree

Notice in this case that we’ve got a complete tree; we did not use the Empty constructor. What if we had?

[] [title: a perhaps less happy little tree ]
1
2
# Node(Leaf 2, 1, Empty) ;;
- : int tree = Node (Leaf 2, 1, Empty)

Now we have what is perhaps a less happy little tree. The right branch of our little tree is empty. The Leaf 3 has fallen. Now perhaps you can see why we need Empty. Node must have two sub-trees. We can’t just do something like:

[] [title: an erroneous tree ]
1
2
3
4
# Node(Leaf 2, 1) ;;
File "", line 1, characters 1-16:
Error: The constructor Node expects 3 argument(s),
       but is applied here to 2 argument(s)

Because the Node constructor expects to have three components. So Empty is used to designate the absense of a Node or Leaf.

How did I draw that tree above? That’ll have to wait for the next Tree Medititation installment when we’ll discuss things like tree traversal and generating dot files used by Graphviz to create images.

C++ Dusty Corner #5379: 0 Is Sometimes a Special Number

| Comments

I recently discovered the C++ Quiz site and figuring that it’s always good to practice C++ skills I started going through the questions. The third question I encountered gave me some pause… The question was:

According to the C++11 standard, what is the output of this program?

#include <iostream>

void print(char const *str) { std::cout << str; }
void print(short num) { std::cout << num; }

int main() {
  print("abc");
  print(0);
  print('A');
}

Now the obvious response would be “abc065”, but I suspected there was some sort of trickery afoot here. Finally, I just entered “abc065” and of course my suspicion was right: the answer was incorrect. Then I went ahead and “cheated” by pasting the code into a file and compiling it:

$ g++ -o quiz1 quiz1.cpp
quiz1.cpp: In function ‘int main()’:
quiz1.cpp:9:10: error: call of overloaded ‘print(int)’ is ambiguous
print(0);
      ^
quiz1.cpp:9:10: note: candidates are:
quiz1.cpp:4:6: note: void print(const char*)
void print(char const *str) { std::cout << str; }
quiz1.cpp:5:6: note: void print(short int)
void print(short num) { std::cout << num; }

“Umm… ok”, I thought “shouldn’t the int literal 0 be cast to a short automatically? What gives here?”. Maybe clang will give me a more descriptive error message? It’s known for that, right?

$ clang++  -o quiz1 quiz1.cpp
quiz1.cpp:9:3: error: call to 'print' is ambiguous
print(0);
      ^~~~~
quiz1.cpp:4:6: note: candidate function
void print(char const *str) { std::cout << str; }
quiz1.cpp:5:6: note: candidate function
void print(short num) { std::cout << num; }

Ok, so clang didn’t reveal any new information here… other than those fancy tildas. So I went back to the CPP Quiz site and chose “has compilation error” and clicked ‘Answer’ to get the explanation:

Sneaky ambiguous function call.

The statement print(0); is ambiguous due to overload resolution rules. 
Both print functions are viable, but for the compiler to pick one, 
one of them has to have a better conversion sequence than the other. 
§13.3.3¶2: "If there is exactly one viable function that is a better 
function than all other viable functions, then it is the one selected 
by overload resolution; otherwise the call is ill-formed".

(a) *Because 0 is a null pointer constant[1], it can be converted 
implicitly into any pointer type with a single conversion.*

(b) Because 0 is of type int, it can be converted implicitly to a 
short with a single conversion too.

In our case, both are standard conversion sequences with a single 
conversion of "conversion rank". Since no function is better than 
the other, the call is ill-formed.

[1] §4.10¶1 A null pointer constant is an integral constant expression 
(5.19) prvalue of integer type that evaluates to zero(...) A null 
pointer constant can be converted to a pointer type.

Ooookaaayy… so this is one of those occasions where being a C++ programmer is very much akin to being a lawyer: you need to be up on all of the provisos, caveats and special exemptions in the law (or in the spec in this case).

So what happened? Passing ‘0’ to the print function can interpretted as either passing a null pointer to the first print function or as a short 0 to the second, overloaded print function. Ok, so couldn’t any integer being passed to the print function also be interpreted as possibly being a pointer? So as an experiment I changed:

print(0);

To:

print(2);

Of course, then it compiles just fine. So ‘0’ is a special number in this context because it’s also the null pointer constant.

If you are a programming polyglot like me, your first reaction upon realizing this is probably to want to run to the relative safety of gated communities such as OCaml, Haskell or maybe Python where these kinds of incidents just don’t happen (because no pointers -> no NULL -> no special case for 0). …until you realize that those neighborhoods have their own, different quirks and in fact there’s no perfect language (well, except for Lisp, maybe, but which Lisp?).

Sometimes you’ve gotta hang out in the C++ hood with all of the sirens and gunshots in the background in order to get things done. As always, you just need to be very wary while you’re in the C++ hood in order to survive. Fortunately, in this case it’s just a compilation error that seems rather confusing at first, not a segfault.

Sure it’s definitely strange that 0 is a special case integer in this context, but to be fair, how often would you actually run into this situation in C++? I’d guess it would be very rare. In most cases you wouldn’t be passing a ‘0’ literal to a function like that - you’d instead be passing in a variable and even if that variable contains ‘0’, that’s just fine.

Is Growth Really an End in Itself?

| Comments

I had an interview at a startup downtown this last week. This company has revenue and is selling stuff. At one point I asked the Director of Engineering: “So, is the company profitable?”. Apparently this wasn’t the right question to ask. His response was they weren’t trying to be profitable, they were trying to grow. As I was pondering this later it seemed odd to want growth over profitability. But apparently in the topsy-turvy world of venture capital funded startups this makes some kind of sense.

But still, I kind of wonder about this idea of growth for growth’s sake. Isn’t that kind of how cancer works? Or maybe kind of like the growth caused by high fructose corn syrup?

The thing is, these VC funded startups seem to be getting all the press, whereas companies that aren’t obsessed with growth tend to fly completely under the radar. My wife worked for a small software company for most of the 90’s that made scientific visualization software for the Mac. They primarily sell into Universities & Government research facilities. It’s a small niche, but for the last 20 years or so they’ve employed between 5 and 8 software engineers. They still employ about that many people and probably will for another 10 years or so. They’re not worried about growth, they want sustainability. And they always seemed to be having a good time. Most of the people working there have been there for close to 20 years now. It’s interesting, steady work that seems to pay well. Sure, they could have gone out and tried to get VC to “expand into new markets”… but it’s probable that if they had done that, they wouldn’t exist now. They may have been bought and rolled into a larger company and most of the people working there would have left soon after that or rapid growth could have caused it to crash and burn. No, instead they’ve chosen the sustainable path. Good on them.

Using the Graphics Module in the OCaml Toplevel

| Comments

First Post

| Comments

This is my GitHub blog.

Here’s a test code snippet:

Discover if a number is prime
1
2
3
4
5
class Fixnum
  def prime?
    ('1' * self) !~ /^1?$|^(11+?)\1+$/
  end
end

Test Gist embedding: