Re: [Caml-list] Functional design for a basic simulation pipe.

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

On Thu, 2007-10-11 at 07:57 +0100, Hugo Ferreira wrote:
> Hello,
> 
> skaller wrote:
> > On Thu, 2007-10-11 at 01:00 +1000, skaller wrote:
> >> On Wed, 2007-10-10 at 11:08 +0100, Hugo Ferreira wrote:
> >>> Hello,
> >>> Apologies for being so obtuse but I cannot to see how this solves my
> >>> problem. 
> >>> let exp = a |> b |> c
> > 
> >> A function is a slave, it is *called* with its argument.
> >> you cant *read* the arguments.
> > 
> > BTW: what you want is something like this 'concept demo'
> > I hacked up in Felix (notes below).
> > 
> > 	a -> b -> c -> d ->+
> > 	^                  |
> > 	|                  |
> > 	+--------<---------+
> > 
> 
> Basically yes. Closer to this though:
> 
>  	a -> b -> c -> d ->+-> e -> f
>  	^                  |
>  	|                  |
>  	+--------<---------+
> 

I know the design I showed didn't match your specifications:
it was only intended as a (working) demo of the idea of
a 'chips and wires' model.

> The solution below is basically the same suggestion I got (in Ocaml)
> from someone else. I guess this is the way to go then.

Unfortunately (at least without control inversion patch) it is not
possible to do this in Ocaml without using pthreads.

It is possible to *emulate* it, as I mentioned, using some
combinator libraries, but to make this work you have to structure
your code in a rather 'peculiar' way to allow the combinators
to actually work: the combinator style approach has the disadvantage 
(in Ocaml without control inversion patch) of an un-natural 
programming form.

The pthreads/Event module based approach is fully natural
but doesn't scale because pthreads don't, and it is inefficient
because it synchronises using primitives designed to support
multi-processing when basic circuits do not need any 
parallelism.

In addition, pthreads have a termination and deadlocking problem
the cooperative system does not: it cannot deadlock, and there
is no facility to explicitly terminate fibres -- they die when
they become unreachable, so the programmer simply has to ensure
there is no gratuitous visibility. Fibres CAN livelock/starve,
and sometimes you find they die from deadlock unexpectedly
due to a bug. The bottom line is that the chips and wires model
has nice properties BUT it is quite low level and requires
some care to ensure it will work properly. It is, however,
the only option for simulations with a high object count.
Pthreads fail on small numbers (a few K threads). Stack
swapping solutions cannot work on 32 bit machines. On 64 bit
machines they're more viable but either suffer a performance
hit copying the stack or a memory usage hit using VM paging.
[i.e. 4K on most systems, which could be way above the object
size which might be only a few bytes in a cellular automata]

Using the heap works best for large object counts, however
it requires continuation passing support of some kind.

I would have to mention Mlton in passing because it uses a rather
clever system with VM based stack swapping, but the stacks are
actually compacted like the heap: it is quite clever IMO.
I think Mlton also offers more or less transparent interfaces
so code can work with either fibres or pthreads in various mixes
without rewriting the algorithms, which is quite cool.
[But I'm no expert, perhaps Steven Weeks will comment more
authoritatively]

-- 
John Skaller <skaller at users dot sf dot net>
Felix, successor to C++: http://felix.sf.net