On Thu, 2004-07-29 at 14:35, Brian Hurt wrote:
> On 29 Jul 2004, skaller wrote:
> Now, for enums of applicative data structures, this works just fine. But
> for imperitive enums, where getting the current element changes global
> state, they'd have to fake applicative behavior. What this means is that
> they'd have to keep track of the what it returned as next. Basically,
> it'd have to keep an 'a Enum.t option ref around. If it's None, the next
> enum has not been created yet, and you create the next enum and update the
> reference. If it's Some x, you return x, the same value you did last
> time. You'd have to do the same thing with the value returned from curr.
This idea was implemented by me for STL many years ago:
basically you have an input iterator type I, and build
an iterator adaptor container F, which converts I to
a forward iterator by simply buffering the input from
the 'earliest' iterator to the current position.
However, this technique *still* has a problem: the actual
stream destructor is lazy in the sense it is only called
when needed to fetch a never before fetched element.
Unfortunately the lazy evaluation in the Enum package
itself means that time is indeterminate, so you still
lose control over coupled streams.
Just as an example -- and a very nasty one -- consider
a tokeniser and a parser streamed together, and suppose
that after some reduction the parser modifies the tokeniser
to change what it tokenises... then you simply cannot
buffer the tokens, because when you read forward after
modifying the tokeniser, you get the wrong tokens,
since the ones in the buffer used the old rules.
Before you laugh too hard at this example --
THE most common lexer and parser combination
in the world must do precisely what I described,
its called a C compiler :)
In particular the lexer is modified
as soon as a typename is defined so the next identifier
with the same spelling is lexed as a typename keyword
not an ordinary identifier.. Frontc does this, and so do
most C lexer/parser systems AFAIK :)
Anyhow, I think you are right this technique will
solve a lot of problems, and what's more, there
is no general technique that CAN solve them all.
Instead we just specify all imperative enums
must be uncoupled. This is a restriction, and it
may be if you break the rules, Enum still works fine.
The important thing is we don't promise it.
The key thing is to be very clear when the
specified interface semantics hold. For me to use
Enums, even if I know the implementation code backwards,
I need to verify the documented requirements are met
by my application -- for example deciding that the
C lexer parser would break the rules, and would NOT
be a suitable combination to glue together with Enums.
This is fine .. there are plenty of things Enums will
work just fine for.
Here's another example that doesn't work well: Hashtable.
Weird -- but what happens if you iterate a hashtable
and insert and delete inside the argument function?
The result may include 'deleted' elements, and fail
to include some inserted ones.
I actually have this problem in Felix compiler,
I had to convert to a Set to control the process:
Hashtbl.iter just isn't all that useful: Set.choose
is a much better function: its a stream iterator,
whereas all those functions in Ocaml called 'iter'
are NOT in fact iterators at all -- the control
relation is inside out.
This is again a coupling problem .. and the purely
functional approach neatly sidesteps it, despite
the algorithm actually being procedural (choose an
element from a set .. assign the set to a mutable
field with the element removed .. if more elements
are then added, well, set choose will chose them,
and if they're removed it won't -- the evaluation
order is under control!
[Something about adding a level of indirection solving
all problems in CS .. :]
--
John Skaller, mailto:skaller@xxxxxxxxxxxx
voice: 061-2-9660-0850,
snail: PO BOX 401 Glebe NSW 2037 Australia
Checkout the Felix programming language http://felix.sf.net
-------------------------------------------------------
This SF.Net email is sponsored by BEA Weblogic Workshop
FREE Java Enterprise J2EE developer tools!
Get your free copy of BEA WebLogic Workshop 8.1 today.
http://ads.osdn.com/?ad_id=4721&alloc_id=10040&op=click
|
