Re: [Caml-list] looping recursion

[skaller <skaller@users.sourceforge.net>]

On Thu, 2004-07-29 at 00:36, Brian Hurt wrote:
> On 28 Jul 2004, skaller wrote:
> 
> > On Wed, 2004-07-28 at 11:43, Brian Hurt wrote:
> > > On Tue, 27 Jul 2004 briand@aracnet.com wrote:
> > 
> > > Very long lists are a sign that you're using the wrong data structure.
> > 
> > What would you recommend for a sequence of tokens?
> > Streams are slow and hard to match on.. bucket lists
> > have lower storage overhead but hard to match on.
> 
> Extlib Enumerations.  For short lists, yeah they're slower than lists.  

That doesn't matter -- the lists are long by specification.

> But for long lists, I could see them being a lot faster.  Don't forget 
> cache effects- streaming processing can have much better cache behavior 
> than repeatedly walking a long list (too large to fit into cache). 

Can't pattern match on them. One reason for building
a list is I filter it, for example, in Felix I strip out white space
tokens, in Vyper (Python interpreter written in Ocaml)
I did something like 13 separate passes to handle
the indentation and other quirks to precondition the input
to the parser so it became LALR(1).

So, I'd have to use a list as a buffer for the head of the stream
anyhow..

Also, there is a serious design problem with ExtLib Enums.
Although the data structure appears functional, it doesn't
specify when things happen precisely.

In particular if the input is a stream, that is, uses 
mutators to extract elements, then instead of using
the persistence and laziness so you can use the Enums
as forward iterators -- for example in a backtracking
parser -- the Enums actually degrade to uncopyable
input iterators.

Since Ocamllex uses a mutable lex buffer, the Enums
based on them are also non-functional input iterators ..
[I can get around that by calling 'force()' but that
totally defeats the purpose of using Enums .. :]

Whereas, a plain old list is a purely functional
forward iterator, and unquestionably works with
a backtracking parser.

As an example of a simple modification I could do that
won't work easily with uncontrolled control inversion:
suppose I cache the token stream on disk, and in
particular Marshal file 'fred.flx' out as 'fred.tokens'.
[Now you *have* to force() all the iterators, or
each one inside the #include will write the file
to disk at the end of the sub-file .. but that 
should only be done once -- its quite slow writing
a file to disk .. forcing all the enums makes
separate copies of the tokens .. argggg .. ]

The problem goes away when I manually build lists
and preprocess them because I have explicit control.

Bottom line is that Enums work fine to integrate
purely functional data structures together but they're
not very useful mixing coupled streams together.

Crudely -- if you have a hierarchy of streams
you may need to read them in a particular order
due to the coupling .. with STL input iterators
you can do that, with hand written Ocaml
you can do that -- with Enums you can't.

-- 
John Skaller, mailto:skaller@users.sf.net
voice: 061-2-9660-0850, 
snail: PO BOX 401 Glebe NSW 2037 Australia
Checkout the Felix programming language http://felix.sf.net



-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners