[Haskell-cafe] Re: Mathematica

[Jon Harrop]

On Tuesday 12 June 2007 18:41:34 Tomasz Zielonka wrote:
> On Sun, May 13, 2007 at 02:19:55PM +0100, Andrew Coppin wrote:
> > Writing *insanely* efficient number chrunking software requires a deep
> > understanding of the target architecture, and lots of playing with very
> > low-level constructs. Assembly is really the only language you can do it
> > with; even C is probably too high-level.

Just reuse existing libraries: BLAS, LAPACK, ATLAS, FFTW. The free libraries 
that I have benchmarked were all much faster than Mathematica. FFTW was 4x 
faster on average, for example.

> > The "notebook" interface is very sophisticated and clearly beyond the
> > capabilities of any current GUI toolkit for Haskell. (Implementing this
> > would be approximately as hard as writing a full web browser in Haskell.)

Yes. Our technical presentation software took 6 man months but it supported 
antialiasing, real-time visualization and zooming and panning of the whole 
GUI. A simple notebook interface rendering to OpenGL would only be ~20kLOC of 
OCaml/Haskell.

> > The pattern matching engine could be implemented, but it's not a trivial
> > task. Mathematica's pattern matching is quite sophisticated. It would
> > take someone a while to do, that's all.

Beyond the pattern matchers in ML and Haskell, Mathematica adds sequence 
patterns. These just search linear sequences or permutations completely 
naively.

For example, the obvious implementation of the higher-order map function has 
quadratic complexity because Mathematica eagerly copies entire sub arrays "t" 
unnecessarily:

  map[_, {}] := {}
  map[f_, {h_, t___}] := Prepend[map[f, {t}], f h]

Moreover, it does no decision-tree optimizations. Instead, it only optimizes 
patterns in the symbol table (called "DownValues") that contain only single 
static symbols into a hash table (called a "dispatch table"):

  f[a] = 1
  f[b] = 2
  ...

There are some undocumented tricks but you can achieve the same asymptotic 
performance quite easily, e.g. hashconsing and memoization.

-- 
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
OCaml for Scientists
http://www.ffconsultancy.com/products/ocaml_for_scientists/?e