Hello

Here is the latest Caml Weekly News, for the week of 30 August to 06 September, 2005.

- Restarting a piece of code
- ocaml-gui mailing list
- GUIs and ocaml
- Polymorphic variants and scene graphs
- Unix.localtime not threadsafe?
- Existential types
- Offre d'emploi a l'IRISA

Archive: http://thread.gmane.org/gmane.comp.lang.caml.general/30289

> I have a problem which I do not know how to program in The Right Way. > I would be grateful to hear ideas on how to do it. > > Suppose I have a bunch of functions (the actual example is exact real > number arithmetic) which optimistically compute results (e.g. we compute > numbers up to some precision and hope it will be good enough) that may > turn out not to be good enough later during the computation. When this > happens, the entire computation needs to be restarted (e.g. we need to > recompute the numbers again with higher precision). This is a very interesting idea. Something similar comes up in my AS/Xcaml application server when an HTTP resource which has already computed a portion of the HTTP response realizes that it cannot continue and must delegate the response to a different HTTP resource. An exception is raised which is caught by the AS/Xcaml runtime system, which aborts the current computation and restarts the computation of the request by activating the HTTP resource whose URL is provided in the exception body. *** Back to your question, I suggest not to represent computations as thunks but to use continuation passing style. This programming paradigm provides enough flexibility to allow for different overflow thresholds in different parts of the computation, without need for globals and side effects (yes, you should worry about them, they are the bad guys). exception Overflow let grow_threshold old_value = ... let compute threshold threshold_transformation computation = try computation (threshold_transformation threshold) with Overflow -> let new_threshold = grow_threshold threshold in computation (threshold_transformation new_threshold) Recursive computations occur through the compute driver, which also receives a threshold_transformation function determining the value of the threshold for the next computation. If you want your code to be parametric with respect to the threshold growing policy, you might want to modify the code as follows (-rectypes required!) let rec compute grow_threshold = fun threshold threshold_transformation computation -> try computation (compute grow_threshold) (threshold_transformation threshold) with Overflow -> let new_threshold = grow_threshold threshold in computation (compute grow_threshold) (threshold_transformation new_threshold) In this case the driver for recursive computations is no longer the global compute function but the first parameter of the computation function.

> Can we avoid having to pass treshold around directly? You can imagine > that users won't be too thrilled about this sort of thing. I think you can. See arithmetic functions as building blocks for computations---rather than computations themselves---which are parametric with respect to the threshold value. let unit_expression _ = assert false let imaginary_unit_expression _ = assert false let addition_expression _ = assert false let negative_expression _ = assert false let multiplication_expression _ = assert false let inverse_expression _ = assert false let exponential_expression _ = assert false let logarithm_expression _ = assert false exception Overflow let rec compute grow_threshold threshold_transformation = fun computation threshold -> try computation (compute grow_threshold) (threshold_transformation threshold) with Overflow -> let new_threshold = grow_threshold threshold in computation (compute grow_threshold) (threshold_transformation new_threshold) (* Here we define the primitive operations of the algebraic structure *) (* We don't mind if the primitive operations are a little heavy, so *) (* long as it is easy to compose them to form complex computations. *) let one = fun compute threshold -> unit_expression threshold let i = fun compute threshold -> imaginary_unit_expression threshold let add x y = fun compute threshold -> let x' = compute x threshold in let y' = compute y threshold in addition_expression x y threshold let neg x = fun compute threshold -> let x' = compute x threshold in negative_expression x threshold let mul x y = fun compute threshold -> let x' = compute x threshold in let y' = compute y threshold in multiplication_expression x y threshold let inv x = fun compute threshold -> let x' = compute x threshold in inverse_expression x threshold let exp x = fun compute threshold -> let x' = compute x threshold in exponential_expression x threshold let log x = fun compute threshold -> let x' = compute x threshold in logarithm_expression x threshold (* Let's say these are all the basic computations we need. Now we can *) (* start building more computations on top of these. *) let sub x y = add x (neg y) let div x y = mul x (inv y) let pow x y = exp (mul (log x) y) let root x y = exp (mul (log x) (inv y)) let two = add one one let twoi = add i i let cos x = div (add (exp (mul i x)) (exp (neg (mul i x)))) two let sin x = div (sub (exp (mul i x)) (exp (neg (mul i x)))) twoi > I sense monads. Or am I looking for dynamic binding? You are looking for partial evaluation/multistage programming, but you don't necessarily have to delve into MetaOcaml to solve your problem. As you can see you can generate a homomorphism from the calculus of imaginary numbers to the calculus of computations of imaginary numbers which can be directly represented in Ocaml.

Archive: http://thread.gmane.org/gmane.comp.lang.caml.general/30348

I have created a Google group to discuss about GUI issues in/with OCaml. For those interested by the subject... Homepage: http://groups.google.com/group/ocaml-gui Group email: ocaml-gui@googlegroups.com Description: Mailing list to discuss design and development of a cross-platform Graphic User Interface for the OCaml language

Archive: http://thread.gmane.org/gmane.comp.lang.caml.general/30293

> May I add another question to this thread: What do people think of > OCaml's GUI libraries in terms of stability? Well there are not that many libraries for GUIs in ocaml. We have : - LablTk/CamlTk - LablGTK - Wxcaml [1] - OCaml-Win32 [2] Are there any others ? [1] http://pllab.kaist.ac.kr/~shoh/ocaml/wxcaml/doc/ [2] http://www.speakeasy.org/~hchomsky/ocaml-win32.html

> If anyone is seriously considering writing bindings for Cairo from > OCaml then I'd like to know. Gah! they already exist : http://cairographics.org/cairo_2docaml (No tarballs, only in the CVS repository).

> I had better clarify before continuing. I see two viable approaches here: > > 1. Write OCaml bindings to the native GUIs and then an OCaml wrapper that > abstracts the nativeness away. > > 2. Write a new widget toolkit designed to render via OpenGL. > > If we do (1) then it will handle skinning and the intersection of the sets of > functionality of the native GUIs. > > If we do (2) then customisation and skinning will be ignored but you have the > advantage of real time 2D and 3D graphics. > > Option (2) seems much easier and more useful to me. I've never cared about > skinning... Well, in option (1), as somebody else underlined it, it is a lot more than just skinning. How do you handle i18n and l10n issues? How to display bidirectionnal languages? How to write Arabic, Hebrew or Chinese characters? How to take input in Japanese or Tamil? How to handle copy/paste and drag & drop with other applications of the platform? Or to print PDF with Arabic and Indian characters in the same document? Maybe you don't have those issues for you local market, Jon. But as soon as you are writting graphical applications to be used worldwide, those issues are coming out pretty quickly. This is at least a requirement for my application. I really fear your under estimate the amount of work needed to accomplish such a job. And the OCaml community seems pretty fragmented on this GUI front. To improve on the situation, I see following options: 1. improve Labgtk2 documentation and use Gtk2 on all patforms. As our try on Win32 have shown, compiling Gtk2 on Windows seems pretty complicated and a moving target, albeit not impossible to do. I don't know for MacOS X. And Gtk2 behaviour is different on Win32 than native Win32 applications; 2. write a *simple* GUI front end, in OCaml, with only simple modules and/or simple objects. No fancy use of OCaml type system. Stay close to ML core. Use Labgtk2, native Win32 and MacOS X libraries to render the GUI. However I don't know the complexity of handling gory details, like encoding of strings; 3. (Jon option) write a pure GUI from scratch, in pure OCaml. A project similar to Qt or WxWidgets for C++. It seems doable to have a basic GUI but handling all i18n and desktop interoperability issues seems pretty complicated; 4. Use Labltk. I can't really comment on it, as I have never used it and can't say about its graphical behaviour or desktop integration (copy/paste and drag&drop); 5. drop OCaml to write GUI. Use other languages (usually C++) to make front-ends and use OCaml code only as backend, communicating through sockets or shared memory. Maybe the most viable long term solution. Personnally, I don't know what decision to take. My current GUI code is in Lablgtk2 but, as stated in other emails, use of Gtk2 is too difficult for me. And I don't want to go into another reinvent the wheel syndrom. (sigh)

> > I'm not sold on the idea of a "simple" GUI front end. > > I am. My idea is this: GET RID OF CALLBACKS. > The idea is to use (user space) threads instead. > > The big problem with GUI's is that they're passive. > You write 'event handlers' and have to store the current > state manually. By control inverting the code, you can > just use a thread for each widget. Joe Armstrong did something like this with Erlang and X called Ex11. Can't remember how it works exactly, but it seems each widget is a thread and can process events independantly of the others. http://www.erlang.se/workshop/2004/ex11.pdf

Archive: http://thread.gmane.org/gmane.comp.lang.caml.general/30378

Here's my first attempt at using the technique described in Jacques' paper "Code reuse using polymorphic variants" to make an extensible scene graph. This could be useful for GUI code because users could easily add their own widgets. First, we define functions to render a polygon or a group (list of scene graphs): type polygon = [ `Polygon of vec2 list ] let render_polygon (`Polygon rs) = GlDraw.begins `polygon; List.iter vertex rs; GlDraw.ends () type 'a group = [ `Group of 'a list ] let rec render_group render (`Group l) = List.iter (render_group render) l type 'a t = [ `Polygon of vec2 list |`Group of 'a list ] let rec render1 self = function | #polygon as polygon -> render_polygon polygon | #group as group -> render_group (render1 self) group This "render1" function needs a Y combinator to implement recursion: let rec render1' t = render1 render1' t That "render1'" function can now be used to render scene graphs containing polygons and groups. Next, we define a function to render an axis-aligned rectangle (e.g. for a button): type rectangle = [ `Rectangle of vec2 * vec2 ] let render_rectangle (`Rectangle (l, u)) = render_polygon (`Polygon [vec2 l.x l.y; vec2 u.x l.y; vec2 u.x u.y; vec2 l.x u.y]) let render2 self = function | #rectangle as rectangle -> render_rectangle rectangle | #t as t -> render1 self t By dispatching over type "t", this render function can now render rectangles as well as polygons and groups. Here's the final "render2'" function: let rec render2' t = render2 render2' t Do polymorphic variants look like the way to go for scene graphs? They are slower than ordinary variants but performance is not so important in scene graph code and, particularly, not in GUI code. Now, we want to add: 1. GL naming to identify which GUI element has been clicked on. 2. A "get_bound" function. 3. Layout functions, e.g. "hbox" and "vbox". 4. GL picking to search for the first GUI element under a mouse click. 5. Rendering of text. and, finally, a selection of widgets.

Archive: http://thread.gmane.org/gmane.comp.lang.caml.general/30384

I was looking at the Unix.localtime implementation, and it appears to me that it's not threadsafe. I'm wondering if anyone can confirm. First off, the underlying localtime call is definitely not re-entrant. The tm data structure is shared among all calls, leading to the possibility of races. What I'm not sure of is whether there can be a race given the locking of the OCaml runtime. Here's the code from gmtime.c in the ocaml distribution: static value alloc_tm(struct tm *tm) { value res; res = alloc_small(9, 0); Field(res,0) = Val_int(tm->tm_sec); Field(res,1) = Val_int(tm->tm_min); Field(res,2) = Val_int(tm->tm_hour); Field(res,3) = Val_int(tm->tm_mday); Field(res,4) = Val_int(tm->tm_mon); Field(res,5) = Val_int(tm->tm_year); Field(res,6) = Val_int(tm->tm_wday); Field(res,7) = Val_int(tm->tm_yday); Field(res,8) = tm->tm_isdst ? Val_true : Val_false; return res; } CAMLprim value unix_localtime(value t) { time_t clock; struct tm * tm; clock = (time_t) Double_val(t); tm = localtime(&clock); if (tm == NULL) unix_error(EINVAL, "localtime", Nothing); return alloc_tm(tm); } If I understand the way ocaml's locking works, another thread could make a call to localtime where alloc_small is called. If there are mixed C threads and Ocaml threads, then a call by the C thread at that point could muck up the tm data structure before switching back to OCaml, thus leading to bad data getting into the tm data structure. So, does this seem like a going bug? We think we may have encountered this in the wild, so this may be more than a theoretical bug.

> I don't think the glibc/Linux localtime() man page explicitly states > this, but I expect that it returns a pointer to a *thread-local* > statically allocated struct tm... in which case there's no problem. > > Most other system functions whose API looks non-threadsafe do the same. > ('errno' would be the standard example). Thread-local storage is a recent innovation in the Linux camp. Previously, developers seem to think that no efficient implementation was possible. That's why there all the *_r variants (such as localtime_r). I believe Solaris does something in the direction you suggest.

As others mentioned, the C library implementation of this function could use thread-local storage to avoid this particular race. I don't think this is guaranteed, though. > If I understand the way ocaml's locking works, another thread could > make a call to localtime where alloc_small is called. No, at least not another Caml thread: GC triggered from C code (e.g. alloc_small()) cannot cause context switches. So, from a Caml standpoint, the call to localtime() and the following allocation of its result are atomic. > If there are mixed C threads and Ocaml threads, then a call by the C > thread at that point could muck up the tm data structure before > switching back to OCaml, thus leading to bad data getting into the > tm data structure. Yes, this is possible in principle if 1- some non-Caml threads call localtime(), and 2- the implementation of that function does not use thread-local storage.

For information : Mac OS X use thread-local storage since version 10.2.

Archive: http://thread.gmane.org/gmane.comp.lang.caml.general/30410

> I use an abstract type and a one-way typecast operator to implement > existential quantification; e. g. > > type 'a t > type unknown_t > let some (v : 'a t) = ((Obj.magic v) : unknown_t t) > > Good? This is a standard technique that is used in labltk for instance. There should be no problem as long as your ['a t] type has a uniform representation (i.e. this use of magic only encodes more refined type distinctions.) Note that if your values are implemented in ocaml, there is a reasonable possibility that you could avoid the magic altogether. And if this is not the case (i.e. implemented in ocaml but magic required), there is a serious risk that this is actually unsound. Remember that the function Obj.repr of type ['a -> Obj.t] is unsound, contrary to the intuition. Which leads to the rule of thumb: the only "safe" uses of magic are when dealing with "unsafe" values (implemented in C.) By the way, I'm not sure I would call this existantial quantification, as it is only one-way. This looks more like a simple form of subtyping.

Archive: http://thread.gmane.org/gmane.comp.lang.caml.general/30412

L'unité de Recherche INRIA de RENNES recrute sur contrat à durée déterminée (appellation ingénieur expert) : 1 Ingénieur recherche & développement Lieu de travail : INRIA-Rennes Projet d'accueil : Lande Début du contrat: entre le 1/09/05 et le 31/12/05 Durée du contrat : 12 mois Formation requise : doctorat, DEA, DESS, M2R ou M2Pro en Informatique Activité du Projet d'accueil: Le projet Lande est une équipe de recherche qui s'intéresse à la vérification formelle de logiciels. En particulier, Lande travaille en partenariat avec France Telecom R&D et Thomson R&D sur la vérification de protocoles cryptographiques. Lande développe une technique de vérification automatique, à l'état de prototype, qui a déjà été appliquée avec succès à des protocoles cryptographiques industriels. Objectif du poste: A partir des techniques développées par l'équipe Lande, l'objectif est de réaliser un outil complet, intégré et open source pour la vérification de protocoles cryptographiques. Les protocoles visés sont des protocoles de commerce électronique et de diffusion de contenu video numérique. Ce travail sera réalisé en collaboration avec France Telecom R&D et Thomson R&D. Qualités requises: - solide expérience dans le développement d'applications complexes en Objective Caml. - autonomie - expérience du travail en équipe - anglais courant - des connaissances dans le domaine de la vérification et/ou des protocoles cryptographiques seraient un plus Contact: Thomas.Genet@irisa.fr (http://www.irisa.fr/lande/genet) Thomas.Jensen@irisa.fr (http://www.irisa.fr/lande/jensen)

Here is a quick trick to help you read this CWN if you are viewing it using vim (version 6 or greater).

:set foldmethod=expr

:set foldexpr=getline(v:lnum)=~'^=\\{78}$'?'<1':1

zM

If you know of a better way, please let me know.

If you happen to miss a CWN, you can send me a message and I'll mail it to you, or go take a look at the archive or the RSS feed of the archives.

If you also wish to receive it every week by mail, you may subscribe online.