On Tue, 2004-08-24 at 17:20, Jesse D. Guardiani wrote:
> skaller wrote:
> >You made the list. "All of the pointers" are only gone
> >if you're stupid enough to forget them, and you also
> >unlinked the node <of course I mean 'you' in the general
> >sense not you personally>
> >YOU unlinked the node, you can't cry if you did that
> >and then you can't find the next node -- because
> >YOU made it so that there wasn't one.
Partly that is because you have named symbols,
and if when you come to need the 'next' node,
you rapidly discover it if you don't have the right
symbol hanging around, and the type system
will stop you using a symbol with the right name
and wrong type.
However, this is no guarrantee. I frequently
pass the wrong integer to a function -- I have lots
of integers hanging around. Usually it isn't a gratuitous
error either -- I need to pass the index of a function,
so I pass a thing named 'caller' -- only I should have
passed 'callee': I didn't pass '1' or 'length_of_x' so
even a type abstraction wouldn't have helped.
> I'm primarily concerned with this happening by accident, in a way that isn't
> obvious, but the test code I've written so far seems to indicate that
> it's not
> as easy to slip up as I originally thought.
But still possible. As it always will be.
It's probably quite hard to measure in test code how
easy it will be to slip up -- hard enough with 200 users
over a period of 5 years to really know.
> OK, fair enough. I've never actually written any threaded code.
That doesn't matter -- it isn't anything all
that special, IMHO. Typically if you know what you want
to do, it isn't that hard to implement something.
As usual, if you have trouble knowing your implementation
is doing the right thing -- its a good idea to question
whether you really understand what it is you're trying
> Perhaps it's my lack of actual multi-threading experience that is the
Not really. What's happening here, IMHO, is that we're arguing
back and forth about how to build library components.
There's no simple answer. There are very few good 'rules'
on how to make reuable components.
To some extent we have to rely on principles like
'simple is good'. For exampe, threading introduces
some nasty problems and one solution is simply
to ignore them. You just assume that if you provide
simple enough primitives, they can be wrapped up
in an MT safe way (whatever that means).
A rule I do try to adhere to is 'don't use global variables'.
I try to make reentrant code even when I can't think
of a good reason -- one invariably pops up down the track :)
Similarly you'd assume that your set of primitives
and data structure can be wrapped easily into a more
constrained -- or more complex -- data structure.
> At best, it might actually prove to be safe, reliable,
> and useful.
You need to think about what you mean by 'safe'.
One definition is that all the publically accessible
functions preserve some invariant.
With the 'head' based list, the invariant is stronger
than just the dlink invariant -- so it is harder
to preserve. This also means the head list has a
smaller domain of application, however, within that
domain it provides stronger guarrantees.
For example my Felix compiler which needs lists
of instructions -- it needs to support empty lists,
and I need to know mutations won't gratuitously
propagate to other function's instructions.
An interesting example -- write a procedure that
takes my set of functions, and applies the CPS transformation.
One of the transforms is:
call f a;
is replaced by
jump f a blah2_cont
and so the algorithm may profit by literally chopping the
original instruction stream in two pieces. Your head based
kind of list probably provides the kind of guarrantee
I need, which I lose using the node based lists.
However it seems useful to make the node based lists
first, and implement the head based lists using it,
because then we can reuse code already ensuring
the 'dlink invariant' and focus on the additional
invariants of a head list (such as - the list is linear).
John Skaller, mailto:skaller@...
snail: PO BOX 401 Glebe NSW 2037 Australia
Checkout the Felix programming language http://felix.sf.net