[Caml-list] exene and ocaml ?

[Caml-list] exene and ocaml ?

[briand]

I'm new to ML and have been wondering the ML landscape looking for
nifty ML related tidbits when I ran across exene (http://people.cs.uchicago.edu/~jhr/eXene/).

Has anyone in the ocaml community ever even considered porting this to
ocaml ?  I noticed that it requires threading.  Does anyone have an
opinion as whether ocaml's threads would be compatible with such a
system ?

Thread based gui implementations are the way to go (aren't they ?)

I have been working with labgtk and I've noticed that it suffers from
the underlying limitations of gtk, i.e. it's pure event based.  So
consider an interactive routine to draw a line:

event mouse_button:  draw_line with mouse_button event
event_key: draw_line with key_event
event_motion: draw_line wtih motion_event
...

draw_line event_variant :

dispatch on event

  do something with a GLOBAL variable (or module local ?) !

  pass state information back to main routine to signal change of
  state, e.g. escape key has stopped line drawing mode


YUCH.

Consider the much more elegant and functional implementation:

new line = draw_line event_stream

draw_line event_stream
  consume events until done
  return tuple (success/fail, line object)

I'd rather program the second way.  I think exene lets you do that.

I think that maybe a fudgets style interface might also work well, but
I have a harder time understanding how fudgets work.

OK, well I've used up by nightly bandwidth for the caml-list.

Thanks

Brian


-------------------
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

Re: [Caml-list] exene and ocaml ?

[Ville-Pertti Keinonen]

On Apr 1, 2004, at 7:08 AM, briand@aracnet.com wrote:

> Has anyone in the ocaml community ever even considered porting this to
> ocaml ?  I noticed that it requires threading.  Does anyone have an
> opinion as whether ocaml's threads would be compatible with such a
> system ?

It seems eXene doesn't depend on first-class continuations directly, so 
a port may be possible.  CML threads are several orders of magnitude 
more lightweight than OCaml threads and are garbage collected (they 
disappear if they are blocked in a state that they could not wake up 
from), so a direct port is IMHO probably not worth attempting.

> Thread based gui implementations are the way to go (aren't they ?)

It's one way to do things, but by no means the only way.  A 
single-threaded event model works reasonably well for GUIs, especially 
in most current languages where threads are needlessly expensive.

> Consider the much more elegant and functional implementation:
>
> new line = draw_line event_stream
>
> draw_line event_stream
>   consume events until done
>   return tuple (success/fail, line object)

How is this approach dependent on threads?  I don't know about lablgtk, 
but something like the above is generally possible by recursively 
calling the main event loop with the appropriate locally added 
handlers.  You can escape your modal loop without modifying "globals" 
(I don't see why state variables would need to be global) e.g. using 
exceptions (or continuations, which in OCaml would require using CPS 
for the event loop).

-------------------
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

Re: [Caml-list] exene and ocaml ?

[skaller]

On Thu, 2004-04-01 at 17:25, Ville-Pertti Keinonen wrote:
> On Apr 1, 2004, at 7:08 AM, briand@aracnet.com wrote:
> 
> > Has anyone in the ocaml community ever even considered porting this to
> > ocaml ?  

> > Thread based gui implementations are the way to go (aren't they ?)

You may be interested in Felix. Control inversion is a central
concept, that is, translating a program that reads events
into an event driven one, automatically. Felix threads
are cooperatively multi-tasked, the system supports
millions of threads and fast O(1) switching is possible.

At present, Felix generates C++, however the control inversion
mechanism isn't language specific, all it requires is classes with
methods, and some kind of switch statement. Ocaml has both,
so retargetting to Ocaml may be possible. The back end isn't
fully decoupled from the front end yet though, and the lack
of a goto in Ocaml may impact performance. On the other hand
the Ocaml GC is bound to be superior to the naive implementation
I provide.

> It's one way to do things, but by no means the only way.  A 
> single-threaded event model works reasonably well for GUIs, especially 
> in most current languages where threads are needlessly expensive.

Event driven programming model requires manual
state management. In losing the stack, the most powerful
structuring tool available to the progammer is lost,
and the damage is severe. Simple GUI are easy to get going
but more complex ones are almost impossible to write.

Felix is designed to use a threading programming model,
but an event driven implementation: the best of both worlds.
It's specifically designed to cope with telecommunications and games,
both of which require extremely high performance, and both
of which are almost impossible to program with conventional
programming models. 

> How is this approach dependent on threads? 

In a GUI, there is a notion of a thread for each
window. The locus of control is an important
part of the state. This makes each window an active
process which consumes events.

In an event driven model, control is dispatched
in a displeasing way that requires the locus
of control for each window to be lost.

[Replace 'window' with 'widget' or 'sprite'
or 'active agent' or 'anything you like to think
of as *in control* rather than *being controlled*']

> You can escape your modal loop without modifying "globals" 
> (I don't see why state variables would need to be global) 

Simple: there is no stack. Event handlers have to return,
and when they do the stack is lost.

Of course, you can partition your global state space
into objects, but that in no way changes the fact
the state space is still global.

If you make linked lists of objects, then of course
you can emulate a stack. The question is: why should you
do all the housekeeping to manage stacks when the
functional and structured programming models do it for you.

There is a good reason why you write:

	f = open("filename");
	d = f.read();
	..
	f.close()

The operating system implements control inversion because
an event driven program that reads a file:

	method receive_data d = ...

would be make it rather hard to encode algorithms.

Control inversion of file handling is so important
it is central to the operating system concept: one could say
that a DOS (Disk Operating System) system has one primary
function: control inversion of file handling.

-- 
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

Re: [Caml-list] exene and ocaml ?

[Ville-Pertti Keinonen]

On Apr 1, 2004, at 11:19 AM, skaller wrote:

> Event driven programming model requires manual
> state management. In losing the stack, the most powerful
> structuring tool available to the progammer is lost,
> and the damage is severe. Simple GUI are easy to get going
> but more complex ones are almost impossible to write.

Yes, my "reasonably well" was in the context of current expectations 
and tools.  I'd really love for OCaml to have efficient threading 
(especially if they were implemented using continuations).

I wouldn't use or recommend a massively multithreaded approach unless 
there was a practical and efficient enough environment available.  CML, 
Oz and presumably Felix would be efficient enough in their threading 
concepts, but don't seem to have the real-world practicality of OCaml 
(or mainstream languages).  I'll admit to not having tested Felix yet, 
although I've downloaded it quite some time ago.

> Simple: there is no stack. Event handlers have to return,
> and when they do the stack is lost.

In Brian's specific example as I understood it, this would not be 
relevant.

> Of course, you can partition your global state space
> into objects, but that in no way changes the fact
> the state space is still global.

In this sense, threads are also global state, as would be lazy streams, 
coroutines or whatever means of encapsulating state you use.

-------------------
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

Re: [Caml-list] exene and ocaml ?

[skaller]

On Thu, 2004-04-01 at 19:24, Ville-Pertti Keinonen wrote:
> On Apr 1, 2004, at 11:19 AM, skaller wrote:

> Yes, my "reasonably well" was in the context of current expectations 
> and tools.  I'd really love for OCaml to have efficient threading 
> (especially if they were implemented using continuations).
> 
> I wouldn't use or recommend a massively multithreaded approach unless 
> there was a practical and efficient enough environment available.  

Indeed it would be a disaster to use Posix threads for this ..

> CML, 
> Oz and presumably Felix would be efficient enough in their threading 
> concepts, but don't seem to have the real-world practicality of OCaml 
> (or mainstream languages).  I'll admit to not having tested Felix yet, 
> although I've downloaded it quite some time ago.

Conceptually, Felix is much more 'real world' in some ways than
Ocaml: it is designed to use the C/C++
object model directly, it is designed to allow almost seamless
binding to C/C++ at the source code and object code level.
For example to map a C++ type T for use in Felix you just write:

	type T = "T";

and to make a function

	T f(T);

available you just write:

	fun f: T -> T = "f($1)";

Where Felix misses out on the 'real world' part is of course
maturity: its pre-alpha, and currently there is only one
user who is trying to build a game with it; I don't even
use it myself at this stage (other than building artificial
tests).

--

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

Re: [Caml-list] exene and ocaml ?

[skaller]

On Thu, 2004-04-01 at 19:24, Ville-Pertti Keinonen wrote:
[]

Perhaps I can illustrate with a telco app.
Consider a phone call using a Pre-Paid service.

There is an algorithm which goes like:

(1) Lookup the caller ID and see if they
have a paid up account, if not exit.

(2) Connect to the called number.

(3) On hang up, charge them.

Simple, right? Easy to do with callbacks.

Unfortunately, the real world is more cruel.
It goes like:

Check if the caller has enough money to make
the specified call. If so connect them.

Estimate how long they can remain connected
without running out of money. 
Schedule a disconnection at that time.

Unfortunately, making that estimate is
extremely difficult. Its not like
everyone pays $1 per minute for 
a phone call, no matter where they're calling.

What really happens is you have to check what
kind of plan they have. Then you have to figure
out what they should be paying for the particular
call. The rate may depend on the time of day,
and can change in the middle of the phone call.

The rate also depends on the location being called.
And what time it is there. And on the day of the week.
ANd any special offers ...

As you can imagine that calculation can require
multiple database accesses, and even recursive
calculations with possible trial computations.

Given the weird business rules some telcos implement,
I'd sure HATE to have a system in which each 
database request was satisfied by the DB calling
back with the result of the last query. 

However, that is what physically happens:
the database result is returned asynchronously.
You can't hold the whole phone system up for 30 seconds
while a slow DB is doing a search (but there's no
problem making each caller wait around :D

Using Posix threads here is out of the question.
Even fast multi-CPU Sun boxes cannot switch at anywhere
near the required rate -- but my 500Mhz Linux box
has no trouble outperforming the Sun box
using cooperative threading :D

The reason of course is that selecting the next thread
to run is determined by the next event in the queue
directly, whereas an OS scheduler is asked to choose
a thread on a much more complex basis that involves
concepts like fairness. RT systems are unfair, they
just throw out things they can't do -- in the telco
world it is called 'call gapping' which means 
simply disconnecting people at random to reduce 
the load.

Anyhow the situation is: event driven context
switching is mandatory, but an even driven
programming model is untenable. Three people took
a year to do the C++ version. 1 guy took 3 days
to prototype it in Felix (and he'd never seen Felix
before).

-- 
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

Re: [Caml-list] exene and ocaml ?

[briand]

>>>>> "Ville-Pertti" == Ville-Pertti Keinonen <will@exomi.com> writes:

  >> Simple: there is no stack. Event handlers have to return, and
  >> when they do the stack is lost.

  Ville-Pertti> In Brian's specific example as I understood it, this
  Ville-Pertti> would not be relevant.

Yes I think it would be.  My example was just not very good.

Let's say you have a drawing program with different drawing tools.
Each tool must have local state as it constructs it's respective
graphic object.  If the different events all invoke the procedure
separately, then that state _must_ reside outside of the routine.

In addition, if something happens to change state, i.e. the drawing tool is cancelled, there is no other way to communicate that other than by some sort of global variable.

It may be possible to adress these problems through the use of
modules, but the fact remains, that I can come up with a _much_
cleaner implementation with a persistent procedure than I can with a
standard event model.

As always, there is more than one way to do it, and certainly I can
get things done in the event model approach, but I think it's a
kludge.

Thanks for you comments.

Brian

-------------------
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

Re: [Caml-list] exene and ocaml ?

[briand]

>>>>> "skaller" == skaller  <skaller@users.sourceforge.net> writes:

  skaller> On Thu, 2004-04-01 at 19:24, Ville-Pertti Keinonen wrote:
  >> On Apr 1, 2004, at 11:19 AM, skaller wrote:

  >> Yes, my "reasonably well" was in the context of current
  >> expectations and tools.  I'd really love for OCaml to have
  >> efficient threading (especially if they were implemented using
  >> continuations).
  >> 
  >> I wouldn't use or recommend a massively multithreaded approach
  >> unless there was a practical and efficient enough environment
  >> available.

  skaller> Indeed it would be a disaster to use Posix threads for this
  skaller> ..

Big delay... and then 

I was thinking about that statement... Is that really true ?  If I
only have maybe something like 5-10 threads running, why would it be
such a problem ?

I know almost nothing about the efficiency of posix threads.

Of course the other idea, is that I just run the program in the
virtual machine and use lightweight threads.

>From what I've seen so far, for what I am trying to do the VM may be
good enough.

What does worry me is your comment about garbage collection and
threads.  Are ocaml threads not properly GC'ed ?


Brian

-------------------
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

Re: [Caml-list] exene and ocaml ?

[skaller]

On Sun, 2004-04-11 at 16:46, briand@aracnet.com wrote:

> I was thinking about that statement... Is that really true ?  If I
> only have maybe something like 5-10 threads running, why would it be
> such a problem ?

Probably it wouldn't, but not the reference is to:
  >> I wouldn't use or recommend a massively multithreaded approach

> I know almost nothing about the efficiency of posix threads.

The problem isn't "posix threads" per se, but Unix.
It isn't possible to use Unix kernel scheduling for efficient
task switching. Even highly optimised systems like Solaris
are required to cope with complex conditions which make
it expensive to schedule a time slice.

Also, small address space processors cannot cope
with the linear addressing problem: unlike processes,
threads share address space. If you have a lot of threads
you need a lot of stacks, and they all have to grow
'arbitrarily' large, but there isn't enough address space
for that .. even on a 64 bit machine the position is 
not good.

So actually -- FAR from the garbage collector being
a problem, the situation is exactly the opposite.
It is the heavy memory demands of the linear stack
which creates a problem a GC would have no problem
dealing with.

Felix solves some of these problems by
cooperatively multi-tasking procedural
continuations allocated on a GC managed heap
and allows O(1) event driven scheduling.
The architecture should support a GUI with
one thread for every window (and I mean 
X level window not widget), a game with
10,000 sprites, a telco system managing
100K concurrent phone calls, or any other
problem where you can factor your need
for threads of control into

(1) A few concurrent Unix style threads

(2) A huge number of threads doing almost
no work which can be scheduled on an 
event basis.

A typical architecture would divide the
Unix threads into a worker for each CPU
which drives the cooperative threading
on that CPU, and some I/O threads to
gather and dispatch events between the
worker event queues and the hardware.

This model isn't useful for all problems.
[eg -- it doesn't seem to fit parallel numerical
computing needs]

It also needs augmentation to include
persistence/network transparency to
support mobile agents, for example.

Felix generates C++, but an Ocaml back end
would be quite interesting ..

-- 
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

Re: [Caml-list] exene and ocaml ?

[Richard Jones]

On Sun, Apr 11, 2004 at 06:41:53PM +1000, skaller wrote:
> Also, small address space processors cannot cope
> with the linear addressing problem: unlike processes,
> threads share address space. If you have a lot of threads
> you need a lot of stacks, and they all have to grow
> 'arbitrarily' large,[...]

I did some experiments with early versions of pthrlib (see .sig) where
I tried swapping stacks in and out during context switches using
mmap(2).  All thread stacks were located at the same address in
memory, thus sidestepping the address space problem.  It sort of can
be made to work: It was about 3 years ago, so I forget the exact
problems, but they were probably related to the fact that you need to
back each stack with a disk file, and it doesn't work well with the
normal GROWSDOWN behaviour of stacks.  Plus it's probably a lot slower
because you're trashing the disk cache / data cache and TLB on each
switch.

If you do this you have to be careful not to share data on the stack
between threads (not normally a problem).

BTW, very interesting your comments on Control Inversion.  I think
you're absolutely spot-on with that, and you should write up a node on
the Portland Wiki about it.  I don't think the term "Control
Inversion" is well-known, although it should be.

Rich.

-- 
Richard Jones. http://www.annexia.org/ http://www.j-london.com/
Merjis Ltd. http://www.merjis.com/ - improving website return on investment
PTHRLIB is a library for writing small, efficient and fast servers in C.
HTTP, CGI, DBI, lightweight threads: http://www.annexia.org/freeware/pthrlib/

-------------------
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

Re: [Caml-list] exene and ocaml ?

[skaller]

On Sun, 2004-04-11 at 19:02, Richard Jones wrote:
> On Sun, Apr 11, 2004 at 06:41:53PM +1000, skaller wrote:

> I did some experiments with early versions of pthrlib (see .sig) where
> I tried swapping stacks in and out during context switches using
> mmap(2). 

Would that work with common C++ implementations which
play tricks with the stack for exception handling purposes?

>   Plus it's probably a lot slower
> because you're trashing the disk cache / data cache and TLB on each
> switch.

I don't really understand why the disk cache should be trashed,
at least any more than any other system: if you need backing
store you'll be invoking the VM system any which way .. 

> If you do this you have to be careful not to share data on the stack
> between threads (not normally a problem).

Similar issue in Felix: if you gave a GC for each thread,
you can't share ordinary state data. If you use a global
GC you can, but there may be an impact on overall (and RT) 
performance.

Interesting issue: can you do both at the same time?
And how would you manage it?

Felix certainly allows a GC plus first class C++
objects which are typically using constructor/destructor
memory management for things like strings, and refcounting
for containers, so if you can partition your data then using
multiple memory management systems at once is certainly
possible, but I have no idea what models might exist
for using multiple GC together.. the Ocaml 
collector with 'world stop' incremental collection seems a good
compromise.

-- 
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

Re: [Caml-list] exene and ocaml ?

[Ville-Pertti Keinonen]

In case this was referring to my comment in an earlier message in the 
thread...

On Apr 11, 2004, at 9:46 AM, briand@aracnet.com wrote:

> What does worry me is your comment about garbage collection and
> threads.  Are ocaml threads not properly GC'ed ?

They aren't automatically collected in that they exist until they're 
destroyed or exit...but this is normal for mainstream, heavyweight 
threading systems.  I count OCaml virtual machine threads as 
heavyweight, as well, even though they are lightweight to create, as 
they have scalability problems (O(n) scheduling - counting all threads, 
regardless of state).

I mentioned garbage collection as an example of a specific issue that 
would arise in porting eXene to OCaml.

OCaml/POSIX/Java etc. threads are, in a sense, a different kind of 
programming tool compared to Oz/CML threads or Erlang processes (note 
that Erlang processes are also not garbage collected when unreachable, 
which is even worse in Erlang than other languages, as they are often 
the only way of encapsulating state).  The former kinds of threads are 
suitable for explicit parallelism (e.g. to take advantage of SMP), but 
poorly suited for concurrency as a conceptual programming abstraction 
(it'll work, but not scale well).

-------------------
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