User-Agent: Thunderbird 2.0.0.23 (Macintosh/20090812)
MIME-Version: 1.0
References: <19209.8773.325233.396932@morse.mittelbach-online.de>           
            <4B0C694B.1080803@residenset.net>           
            <4B0E8600.6000003@residenset.net>,<19215.63158.760427.5070@morse.mittelbach-online.de>
            <A969C9F865F27B428A8E60E39D3CED1522F5AAE763@KIELDERCMS1.open.ac.uk>
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 8bit
Message-ID:  <4B11459C.4070305@residenset.net>
Date:         Sat, 28 Nov 2009 16:45:32 +0100
Reply-To: Mailing list for the LaTeX3 project
              <LATEX-L@LISTSERV.UNI-HEIDELBERG.DE>
Sender: Mailing list for the LaTeX3 project <LATEX-L@LISTSERV.UNI-HEIDELBERG.DE>
From: =?ISO-8859-1?Q?Lars_Hellstr=F6m?= <Lars.Hellstrom@RESIDENSET.NET>
Subject: Re: object type / instance arguments
To: LATEX-L@LISTSERV.UNI-HEIDELBERG.DE
In-Reply-To:  <A969C9F865F27B428A8E60E39D3CED1522F5AAE763@KIELDERCMS1.open.ac.uk>
Precedence: list
Status: R

J.Fine skrev:
> The quadratic running time may be poison.  Once that feature is
> there, users may use it heavily.
> 
> It would be sensible to estimate the running time for a dictionary
> with 100 keys.

Note that even this implementation is strongly linear in the number of
dictionary entries; to notice the quadratic term behaviour you'd rather
have to consider a dictionary where all keys are 100 characters long --
and even then you might discover that linear terms dominate the
complexity, since the inner loop of what contributes that quadratic
term to the complexity is TeX grabbing tokens for a macro argument.

> Here's an alternative suggestion.  When TeX boots, do a 
> \fontdimen\nullfont = 100000

I suppose you mean \fontdimen 100000\nullfont=1sp. I wouldn't be
surprised if there is a 15-bit limit on fontdimen numbers though; there
certainly is such a limit if you get them from a TFM.

> to get sufficient linear memory.  Now write a 'Turing machine' or
> 'CPU' that will use this linear memory (in TeX macros of course).

Oooh! That must be the corniest idea I've seen for months. :-) Impressive!

> One will then be able to implement a linear time dictionary.
> 
> You might find this suggestion a little unusual but after
> investigation I think you will find that it gives a better
> architecture and performance than a pure TeX macros approach.
> 
> I look forward to discussing this.

While I generally enjoy exploring new TeX programming tricks, I don't 
see how this would buy you _anything_ for the problem at hand. What 
this (ab)use of the the fontdimens of \nullfont would provide is a 
compact <number> -> <number> table accessed by saying

   \fontdimen <number> \nullfont

but that's pretty much it. You can use the table for storing the 
transition function of a finite automaton, by combining input symbol 
and current state into an <integer constant>, but setting that up and 
then reacting to the state change will take a couple of macro 
expansions at least, so I doubt you're much better off than if doing it 
purely in terms of macros. There's certainly no extra-tight inner loop 
that you could take advantage of.

If one feels like implementing some new mathematical function -- like 
xor, the float placement bit-fiddling, or GF(16) arithmetic -- in TeX 
then this is probably a useful trick, but otherwise not.

Lars Hellström