Subj : Re: Compiler and an interpreter
To   : comp.programming
From : Jon Harrop
Date : Tue Aug 02 2005 07:11 pm

Gerry Quinn wrote:
>> For example, computing the maximum of 5 and each element of a list in
>> OCaml:
>> 
>>   # List.map (max 5) [1;2;3;4;5;6;7;8;9];;
>>   - : int list = [5; 5; 5; 5; 5; 6; 7; 8; 9]
> 
> And using simple iterative methods in C++ it's just as easy.

Do you honestly think the 13 lines of C++ are "just as easy" as the 1 line
of OCaml? The gap between OCaml and C++ widens as programs get more
complicated.

For example, here's the OCaml code required to compute the set of
"n"th-nearest neighbours in a periodic graph:

  module AtomKey = struct
    type t = int * int list
    let compare = compare
  end

  include Set.Make(AtomKey)

  let add_i = List.map2 ( + )

  let rec nth_nn =
    let memory = Hashtbl.create n in
    function
      0 -> singleton
    | 1 -> fun (i, io) ->
        let nn = bonds.(i - 1) in
        if io = zero then nn else
          let aux (j, jo) s = add (j, add_i io jo) s in
          fold aux nn empty
    | n -> fun ((i, io) as iio) ->
        try Hashtbl.find memory (n, i)
        with Not_found ->
          let pprev = nth_nn (n-2) iio and prev = nth_nn (n-1) iio in
          let aux j t = union (nth_nn 1 j) t in
          let t = diff (diff (fold aux prev empty) prev) pprev in
          Hashtbl.add memory (n, i) t;
          t in

Here's the same thing in C++:

typedef pair< int, vector<int> > Atom;

bool operator<(const Atom &a, const Atom &b) {
  if (a.first < b.first) return true;
  if (a.first > b.first) return false;
  const vector<int> &al=a.second, &bl=b.second;
  vector<int>::const_iterator ita=al.begin(), itb=bl.begin();
  while (ita != al.end() && itb != bl.end()) {
    if (*ita < *itb) return true;
    if (*ita > *itb) return false;
    ita++;
    itb++;
  }
  if (ita == al.end() && itb != bl.end()) return true;
  return false;
}

struct AtomCompare {
  bool operator()(const Atom &a, const Atom &b) const { return a<b; }
};

typedef set<Atom, AtomCompare> AtomSet;
struct Compare {
  bool operator()(const pair<int, Atom> &a,
                  const pair<int, Atom> &b) const {
    if (a.first < b.first) return true;
    if (a.first > b.first) return false;
    return a.second < b.second;
  }
};

typedef map<pair<int, Atom>, AtomSet, Compare> Map;

Map memory;

const AtomSet nth_nn(int n, int i, const vector<int> io) {
  const Map::key_type k=make_pair(n, make_pair(i, io));
  Map::const_iterator m=memory.find(k);
  if (m != memory.end()) return m->second;
  AtomSet s;
  if (n == 0) {
    s.insert(make_pair(i, io));
    return s;
  } else
    if (n == 1) {
      const AtomSet &nn=bonds[i-1];
      for (AtomSet::const_iterator it=nn.begin();
           it != nn.end(); it++) {
        int j = it->first;
        vector<int> jo = it->second;
        for (i=0; i<d; i++)
          jo[i] += io[i];
        s.insert(make_pair(j, jo));
      }
      return s;
    } else {
      const AtomSet
        &pprev = nth_nn(n-2, i, io),
        &prev = nth_nn(n-1, i, io);
      for (AtomSet::const_iterator it=prev.begin();
           it != prev.end(); it++) {
        const AtomSet &t = nth_nn(1, it->first, it->second);
        AtomSet t2;
        set_union(s.begin(), s.end(),
                  t.begin(), t.end(),
                  inserter(t2, t2.begin()));
        s=t2;
      }
      AtomSet s2;
      set_difference(s.begin(), s.end(),
                     prev.begin(), prev.end(),
                     inserter(s2, s2.begin()));
      s=AtomSet();
      set_difference(s2.begin(), s2.end(),
                     pprev.begin(), pprev.end(),
                     inserter(s, s.begin()));
    }
  memory[k] = s;
  return memory.find(k)->second;
}

Not only is the OCaml much shorter than the C++, it is also more robust
thanks to static type checking, more maintainable thanks to better code
reuse and 100x faster thanks to functional programming.

-- 
Dr Jon D Harrop, Flying Frog Consultancy
http://www.ffconsultancy.com

.