MathGroup Archive 2005

[Date Index] [Thread Index] [Author Index]

Search the Archive

Re: Types in Mathematica thread

  • To: mathgroup at smc.vnet.net
  • Subject: [mg62997] Re: Types in Mathematica thread
  • From: Jon Harrop <usenet at jdh30.plus.com>
  • Date: Sat, 10 Dec 2005 06:03:12 -0500 (EST)
  • References: <dmp9na$hi2$1@smc.vnet.net> <200512060504.AAA02828@smc.vnet.net> <dn5ohr$nle$1@smc.vnet.net>
  • Sender: owner-wri-mathgroup at wolfram.com

Daniel Lichtblau wrote:
> Jon Harrop wrote:
>> f[{}] := 0
>> f[{h_, t___}] := 1 + f[{t}]
> 
> This is exactly is it should be. The pattern is reforming a List of
> length one less at every step of the match.

In the current implementation, yes. That makes the current implementation
have asymptotically more complex pattern matching than is theoretically
necessary for an infinite number of patterns, many of which are useful.

>> However, this may get fixed in the future.
> 
> My colleagues often pleasantly surprise me, but I rather doubt the
> complexity of this can be improved.

You just need to lazily evaluate the matched sublists ("t" in this case).
This can be done by implementing a new kind of list that is internally a
reference to a subarray of an existing list. Extracting subarrays (as in my
example) is then O(1) instead of O(n). The only tricky part is making sure
that semantics are unchanged, e.g. referring to all child sublists and
forcing them to be copied explicitly if the parent is mutated.

I've had a play around with this and I think there is a lot of scope for a
radical departure in the internal representation of Mathematica's lists,
using immutable balanced binary trees instead of mutable arrays. This is
exactly the kind of improvement that could be made much more easily if
Mathematica were coded in a functional language. It would be interesting to
play around with a toy implementation, to get a better idea of which
optimisations were most beneficial on real Mathematica programs.

> When you note "conventional implementation" you may have in mind
> complexity that would apply if the inderlying structure were a Lisp-like
> linked list. But a Mathematica List is more akin to what traditionally
> is viewed as an array or vector or table, that is, something with a
> fixed number of "contiguous" elements (which may or may not actually map
> to contiguous entities in storage).

This optimisation applies to any suitable internal representation, including
arrays. For example, it will also equivalently improve the asymptotic
complexity of the following pattern:

  f[t___, h_]

which wouldn't happen if the underlying data structure was a singly-linked
list.

>> The fact that Mathematica distinguishes between up- and down-values is
>> really incidental (a historical artefact). So I think you're
>> over-analysing it.
> 
> I don't see this as artifact. It is important that UpValues behave
> differently in various aspects from DownValues. Maybe I'm
> misunderstanding what you mean by an incidental distinction.

It's been a while since I looked but I can see no objective reason to expose
the distinction. I think the distinction between up- and down-values could
be removed were it not for backward compatibility.

-- 
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/products/ocaml_for_scientists/chapter1.html


  • Prev by Date: Re: Solve Limitations
  • Next by Date: Re: Types in Mathematica thread
  • Previous by thread: Re: Re: Types in Mathematica thread
  • Next by thread: Re: Re: Types in Mathematica thread