[Haskell-cafe] Implementing Mathematica

[Jon Harrop]

On Wednesday 30 May 2007 07:04:31 Jon Harrop wrote:
> 3. The language: the hardest part of reimplementing Mathematica is
> inferring what it means (there are no formal evaluation semantics). Once
> you've done that it is just a case of implementing an extensible term
> rewriter and putting in about 20 core rules. The pattern matcher is well
> under 100 LOC and you can do various things to make it more efficient.
> There are two tricks that vastly improve performance of the rewriter:
> return physically identical results whenever possible, and perform
> substitution and evaluation at the same time rather than as two separate
> passes.

Sorry for replying to myself. :-)

It occurs to me that laziness will eliminate the intermediate data structure 
between substitution and evaluation anyway, so that isn't such a concern in 
Haskell.

However, I can't think how you might return physically identical results when 
possible in Haskell. Essentially, you need a higher-order map function:

  val id_map : ('a -> 'a) -> 'a t -> 'a t

that returns its input when "f x = x" for every x. How might this be done?

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